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$.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2009, 91 (2), pp.305-323
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00340791
Contributeur : Olivier Finkel <>
Soumis le : samedi 22 novembre 2008 - 11:40:27
Dernière modification le : mardi 16 janvier 2018 - 15:39:34
Document(s) archivé(s) le : lundi 7 juin 2010 - 23:14:44

Fichiers

undec-tilings-FI.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

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

Partager

Métriques

Consultations de la notice

171

Téléchargements de fichiers

83