Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Highly Undecidable Problems about Recognizability by Tiling Systems

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 and Muller ones [1]. It was proved in [9] that it is undecidable whether a Büchi-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üchi-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üchi recognizable language of infinite pictures can be accepted row by row using an automaton model over ordinal words of length $\omega^2$.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Olivier Finkel Connect in order to contact the contributor
Submitted on : Saturday, November 22, 2008 - 11:40:27 AM
Last modification on : Saturday, June 25, 2022 - 8:48:33 PM
Long-term archiving on: : Monday, June 7, 2010 - 11:14:44 PM


Files produced by the author(s)


  • HAL Id : ensl-00340791, version 1
  • ARXIV : 0811.3704


Olivier Finkel. Highly Undecidable Problems about Recognizability by Tiling Systems. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2009, 91 (2), pp.305-323. ⟨ensl-00340791⟩



Record views


Files downloads