| Identifiant de l'article : |
 |
ensl-00340791, version 1 |
|
|
| Identifiant arXiv : |
|
arXiv:0811.3704 |
|
|
| Domaine : |
|
|
|
|
| Titre : |
|
Highly Undecidable Problems about Recognizability by Tiling Systems |
|
|
| Auteur(s) : |
|
Olivier Finkel1, 2 |
|
|
| Laboratoire : |
|
| 1 : |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 2 : |
ELM - Équipe de Logique Mathématique |
|
|
|
| Équipe de recherche : |
|
[MC2 - Modèles de calcul et complexité] |
| Résumé : |
|
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$. |
|
|
|
Langue du texte
intégral : |
|
Anglais |
|
|
| Mots-clés : |
|
Languages of infinite pictures – recognizability by tiling systems – decision problems – highly undecidable problems – analytical hierarchy. |
|
|
| Commentaire : |
|
to appear in a Special Issue of the journal Fundamenta Informaticae on Machines, Computations and Universality. |
|
|
Récupérer au format
