Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: languages of infinite pictures

Sortuj według:

Ogranicz wyniki do:

Highly Undecidable Problems about Recognizability by Tiling Systems

Finkel O.

Fundamenta Informaticae

2009

Vol. 91, nr 2

305-323

Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with usual acceptance conditions, such as the Büchi and Muller ones, in [1]. It was proved in [9] that it is undecidable whether a Büchirecognizable language of infinite pictures is E-recognizable (respectively, A-recognizable). We show here that these two decision problems are actually Π1/2/ -complete, hence located at the second level of the analytical hierarchy, and "highly undecidable". We give the exact degree of numerous other undecidable problems for Büchi-recognizable languages of infinite pictures. In particular, the nonemptiness and the infiniteness problems are Σ1/1/ -complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all Π1/2/ -complete. It is also Π1/2/ -complete to determine whether a given Büchi recognizable language of infinite pictures can be accepted row by row using an automaton model over ordinal words of length ω2/.