Computer Science – Computational Complexity
Scientific paper
2008-11-22
Fundamenta Informaticae 2, 91 (2009) 305-323
Computer Science
Computational Complexity
to appear in a Special Issue of the journal Fundamenta Informaticae on Machines, Computations and Universality
Scientific paper
Altenbernd, Thomas and W\"ohrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with usual acceptance conditions, such as the B\"uchi and Muller ones [1]. It was proved in [9] that it is undecidable whether a B\"uchi-recognizable language of infinite pictures is E-recognizable (respectively, A-recognizable). We show here that these two decision problems are actually $\Pi_2^1$-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\"uchi-recognizable languages of infinite pictures. In particular, the non-emptiness and the infiniteness problems are $\Sigma^1_1$-complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all $\Pi^1_2$-complete. It is also $\Pi^1_2$-complete to determine whether a given B\"uchi recognizable language of infinite pictures can be accepted row by row using an automaton model over ordinal words of length $\omega^2$.
No associations
LandOfFree
Highly Undecidable Problems about Recognizability by Tiling Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Highly Undecidable Problems about Recognizability by Tiling Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Highly Undecidable Problems about Recognizability by Tiling Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-721516