Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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 Π1/2/ -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 Σ1/1/ -complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all Π1/2/ -complete. It is also Π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 ω2/.
Wydawca
Czasopismo
Rocznik
Tom
Strony
305--323
Opis fizyczny
Bibliogr. 25 poz.
Twórcy
autor
- 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, finkel@logique.jussieu.fr
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0004-0043