4130649343

algorytmu odpowiadającego na jakieś pytanie dotyczące języka drzew nieurangowanych, który bierze na wejściu automat na drzewach. Załóżmy, że istnieje algorytm odpowiadający na to samo pytanie na podstawie algebry w czasie wielomianowym. Wtedy będzie warto szukać odpowiedzi bezpośrednio na podstawie automatu tylko pod warunkiem, że będziemy umieli to zrobić w czasie krótszym niż wykładniczy.

Nie wszystkie problemy definiowalności, których rozstrzygalność jest znana dla słów są rozwiązane dla drzew. Jednak niektóre wyniki z tego zakresu oraz kilka zastosowań algebraicznych reprezentacji języków drzew jest omówionych w [Bo].

6