Highly Undecidable Problems about Recognizability by Tiling Systems

• Autorzy: Finkel O.
• Języki publikacji: EN

Abstrakty

EN

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, in [1]. It was proved in [9] that it is undecidable whether a Büchirecognizable language of infinite pictures is E-recognizable (respectively, A-recognizable). We show here that these two decision problems are actually Π¹/₂/ -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 nonemptiness and the infiniteness problems are Σ¹/₁/ -complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all Π¹/₂/ -complete. It is also Π¹/₂/ -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 ω^2/.

Słowa kluczowe

EN

languages of infinite pictures; recognizability by tiling systems; decision problem; highly undecidable problem; analytical hierarchy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 2
• Strony: 305--323
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Finkel O.

• Equipe Mod`eles de Calcul et Complexit´e Laboratoire de l’Informatique du Parallélisme CNRS et Ecole Normale Supérieure de Lyon 46, Allée d'Italie 69364 Lyon Cedex 07, France,

Bibliografia

• [1] Altenbernd, J.-H., Thomas, W., Wőhrle, S.: Tiling Systems over Infinite Pictures and Their Acceptance Conditions, Proceedings of the 6th International Conference Developments in Language Theory, DLT 2002, 2450, Springer, 2003.
• [2] Ballier, A., Jeandel, E.: Tilings and Model Theory, Proceedings of the Journées Automates Cellulaires 2008, Uzès, France, 2008.
• [3] Castro, J., Cucker, F.: Nondeterministic !-Computations and the Analytical Hierarchy, Journal Math. Logik und Grundlagen d. Math, 35, 1989, 333-342.
• [4] Cohen, R., Gold, A.: ω-computations on Turing machines, Theoretical Computer Science, 6, 1978, 1-23.
• [5] Darondeau, P., Yoccoz, S.: Proof Systems for Infinite Behaviours, Information and Computation, 99(2), 1992, 178-191.
• [6] Delorme, M., Mazoyer, J., Eds.: Cellular Automata, a parallel Model, Kluwer Academic, 1994.
• [7] Engelfriet, J., Hoogeboom, H. J.: X-automata on !-words, Theoretical Computer Science, 110(1), 1993, 1-51.
• [8] Finkel, O.: Borel hierarchy and omega context free languages, Theoretical Computer Science, 290(3), 2003, 1385-1405.
• [9] Finkel, O.: On recognizable languages of infinite pictures, International Journal of Foundations of Computer Science, 15(6), 2004, 823-840.
• [10] Finkel, O.: Highly Undecidable Problems for Infinite Computations, Journal RAIRO-Theoretical Informatics and Applications, 2008, 32 pages,
• [11] Giammarresi, D., Restivo, A.: Two-Dimensional Languages, in: Handbook of formal languages, Vol. 3, Springer, Berlin, 1997, 215-267.
• [12] Harel, D.: Recurring Dominoes: Making the Highly Undecidable Highly Understandable, Fundamentals of Computation Theory, Proceedings of the 1983 International FCT-Conference, Borgholm, Sweden, August 21-27, 1983, 158, Springer, 1983.
• [13] Harel, D.: Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness, Journal of the ACM, 33(1), 1986, 224-248.
• [14] Hirst, T., Harel, D.: Taking It to the Limit: On Infinite Variants of NP-Complete Problems, Journal of Computer and System Sciences, 53(2), 1996, 180-193.
• [15] Kechris, A. S.: Classical descriptive set theory, Springer-Verlag, New York, 1995, ISBN 0-387-94374-9.
• [16] Landweber, L.: Decision problems for !-automata, Mathematical Systems Theory, 3(4), 1969, 376-384.
• [17] Lescow, H., Thomas, W.: Logical specifications of infinite computations, A Decade of Concurrency (J. W. de Bakker,W. P. de Roever, G. Rozenberg, Eds.), 803, Springer, 1994.
• [18] Moschovakis, Y. N.: Descriptive set theory, North-Holland Publishing Co., Amsterdam, 1980, ISBN 0-444-85305-7.
• [19] Perrin, D., Pin, J.-E.: Infinite words, automata, semigroups, logic and games, vol. 141 of Pure and Applied Mathematics, Elsevier, 2004.
• [20] Prasad Sistla, A.: On Verifying That A Concurrent Program Satisfies A Nondeterministic Specification, Information Processing Letters, 32(1), 1989, 17-23.
• [21] Rogers, H.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.
• [22] Staiger, L.: Hierarchies of recursive !-languages, Elektronische Informationsverarbeitung und Kybernetik, 22(5-6), 1986, 219-241, ISSN 0013-5712.
• [23] Staiger, L.: !-languages, in: Handbook of formal languages, Vol. 3, Springer, Berlin, 1997, 339-387.
• [24] Thomas,W.: Automata on infinite objects, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Formal models and semantics, Elsevier, 1990, 135-191.
• [25] Wolfram, S., Ed.: Theory and Applications of Cellular Automata, World Scientific Press, 1986.