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}
.
