Affiliations: Equipe Modèles de Calcul et Complexité
Laboratoire de l'Informatique du Parallélisme CNRS et
Ecole Normale Supérieure de Lyon 46, Allée
d'Italie 69364 Lyon Cedex 07, France.
[email protected]
Note: [] Adress for correspondence: Equipe Modèles de Calcul et
Complexité, Laboratoire de l'Informatique du
Parallélisme, CNRS et Ecole Normale Supérieure de
Lyon, 46, Allée d'Italie 69364 Lyon Cedex 07,
France
Abstract: 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 andMuller 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}.
Keywords: Languages of infinite pictures, recognizability by tiling systems, decision problems, highly undecidable problems, analytical hierarchy
