No Access

ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES

OLIVIER FINKEL

Equipe de Logique Mathématique, U.F.R. de Mathématiques, Université Paris 7, 2 Place Jussieu 75251 Paris cedex 05, France

Search for more papers by this author

https://doi.org/10.1142/S0129054104002777Cited by:5 (Source: Crossref)

Abstract

In a recent paper, Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Büchi and Muller ones, firstly used for infinite words. The authors asked for comparing the tiling system acceptance with an acceptance of pictures row by row using an automaton model over ordinal words of length ω². We give in this paper a solution to this problem, showing that all languages of infinite pictures which are accepted row by row by Büchi or Choueka automata reading words of length ω² are Büchi recognized by a finite tiling system, but the converse is not true. We give also the answer to two other questions which were raised by Altenbernd, Thomas and Wöhrle, showing that it is undecidable whether a Büchi recognizable language of infinite pictures is E-recognizable (respectively, A-recognizable).

Keywords:

References

J-H. Altenbernd, W. Thomas and S. Wöhrle, Proceedings of the 6th International Conference on Developements in Language Theory, DLT 2002, Lecture Notes in Computer Science 2450 (Springer, 2003) pp. 297–306. Crossref, Google Scholar
N. Bedon, Finite Automata and Ordinals, Theoretical Computer Science 156 (1996) pp. 119–144. Google Scholar
N. Bedon, Langages Reconnaissables de Mots Indexés par des Ordinaux, Ph.D. Thesis, Université de Marne la Vallée, January 1998 . Google Scholar
J. R. Büchi, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik 6, 66 (1960). Crossref, Google Scholar
J. R. Büchi, On a Decision Method in Restricted Second Order Arithmetic (Stanford University Press, 1962) pp. 1–11. Google Scholar
J. R. Büchi and D. Siefkes , The Monadic Second Order Theory of All Countable Ordinals, Decidable Theories 2 , Lecture Notes in Mathematics 328 ( Springer , 1973 ) . Crossref, Google Scholar
Y. Choueka, Journal of Computer and System Sciences 8, 117 (1974). Crossref, Web of Science, Google Scholar
R. S. Cohen and A. Y. Gold, Theoretical Computer Science 6, 1 (1978). Crossref, Web of Science, Google Scholar
J. Duparc, O. Finkel and J. P. Ressayre, Theoretical Computer Science 257(1-2), 85 (2001). Crossref, Web of Science, Google Scholar
O. Finkel, Theoretical Computer Science 255(1-2), 223 (2001). Crossref, Web of Science, Google Scholar
O. Finkel, RAIRO-Theoretical Informatics and Applications 37(2), 105 (2003). Crossref, Web of Science, Google Scholar
O. Finkel, RAIRO-Theoretical Informatics and Applications 37, 115 (2003). Crossref, Web of Science, Google Scholar
D. Giammarresi and A. Restivo, Handbook of Formal Languages 3, eds. G. Rozenberg and A. Salomaa (Springer, Berlin, 1997) pp. 215–267. Crossref, Google Scholar
J. C. Hemmer , Automates sur Mots de Longneur Supérieure à ω ( Université de Liège , 1992 ) . Google Scholar
A. S. Kechris , Classical Descriptive Set Theory ( Springer-Verlag , 1995 ) . Crossref, Google Scholar
L. H. Landweber, Math. Syst. Theory 3, 376 (1969). Crossref, Google Scholar
H. Lescow and W. Thomas, A Decade of Concurrency, Lecture Notes in Computer Science 803, eds. J. W. de Bakkeret al. (Springer, 1994) pp. 583–621. Google Scholar
Y. N. Moschovakis , Descriptive Set Theory ( North-Holland, Amsterdam , 1980 ) . Google Scholar
D. Perrin and J.-E. Pin , Infinite Words, Automata, Semigroups, Logic and Games 141 ( Elsevier , 2004 ) . Google Scholar
W. Sierpinski , Cardinal and Ordinal Numbers ( Polish Scientific Publisher , Varsovie , 1965 ) . Google Scholar
P. Simonnet, Automates et Théorie Descriptive, Ph.D. Thesis, Université Paris 7, March 1992 . Google Scholar
L. Staiger, Jour. Inform. Process. Cybernetics EIK 22 219 (1986). Google Scholar
L. Staiger , ω-Languages 3 , eds. G. Rozenberg and A. Salomaa ( Springer-Verlag , Berlin ) . Google Scholar
W. Thomas, Handbook of Theoretical Computer Science B, ed. J. Van Leeuwen (Elsevier, Amsterdam, 1990) pp. 131–191. Google Scholar
J. Wojciechowski, Proc. Colloquium on "Algebra, Combinatorics and Logic in Computer Science" 2, eds. J. Demetrovics, G. Katona and A. Salomaa (Amsterdam,, North Holland, 1983) pp. 871–887. Google Scholar
Jerzy Wojciechowski, Fundamenta Informatic 7, 191 (1984). Crossref, Google Scholar
J. Wojciechowski, Fundamenta Informaticæ 8, 379 (1985). Crossref, Google Scholar