Complexity of Topological Properties of Regular w-Languages

• Autorzy: Selivanov V.L. , Wagner K.W.
• Języki publikacji: EN

Abstrakty

EN

We determine the complexity of topological properties (i.e., properties closed under the Wadge equivalence) of regular w-languages by showing that they are typically NL-complete (PSPACE-complete) for the deterministic Muller, Mostowski and Büchi automata (respectively, for the nondeterministic Rabin, Muller, Mostowski and Büchi automata). For the deterministic Rabin and Streett automata and for the nondeterministic Streett automata upper and lower complexity bounds for the topological properties are established.

Słowa kluczowe

EN

w-languages; finite automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 197--217
• Opis fizyczny: bibliogr. 25 poz.

Twórcy

autor

Selivanov V.L.

autor

Wagner K.W.

• Institut für Informatik, Julius-Maximilians-Universität Würzburg, Germany,

Bibliografia

• [1] J. L. Balcazar, J. Diaz and J. Gabarro. Structural Complextiy I. Springer 1995.
• [2] J. Cabessa. A Game Theoretic Approach to the Algebraic Counterpart of the Wagner Hierarchy. PhD Thesis, Universities of Lausanne and Paris-7, 2007.
• [3] O. Carton and D. Perrin. Chains and superchains for w-rational sets, automata and semigroups. International Journal of Algebra and Computation 1 (1997), N 7, 673-695.
• [4] O. Carton and D. Perrin. The Wagner hierarchy of w-rational sets. International Journal of Algebra and Computation 9 (1999), N 7, 673-695.
• [5] J. Duparc and M. Riss. The missing link for u;-rational sets, automata, and semigroups. International Journal of Algebra and Computation, 16, No 1 (2006) 161-185.
• [6] S. Krishnan, A. Puri and R. Bray ton. Structural complexity of w-automata. In: Proceedings of the 6th TAPSOFT conference 1995. Lecture Notes in Computer Science, vol. 915, Springer 1995, 143-156.
• [7] L.H. Landweber. Decision problems for o> automata. Mathematical Systems Theory 4 (1969), 376-384.
• [8] C. Loding. Optimal bounds for the transformation of omega-automata. In: Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science 1999. Lecture Notes in Computer Science, vol. 1738, Springer 1999, 97-109.
• [9] A. Meyer and L.J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential time. In: Proceedings of the 13th IEEE Symp. on Switching and Automata Theory 1972, 125-129.
• [10] J.-E. Pin. Syntactic semigroups. In: Handbook of Formal Languages, v. 1 (1997), Springer, Berlin, 679-746.
• [11] D. Perrin and J.-E. Pin. Infinite Words. Vol. 141 of Pure and Applied Mathematics, Elsevier, 2004.
• [12] S. Safra. On the complexity of w-automata. In: Proceedings of the 29th IEEE FOCS 1988, 319-327.
• [13] V.L. Selivanov. Fine hierarchy of regular w-languages. Theoretical Computer Science 191 (1998), 37-59.
• [14] A.P. Sistla, M.Y. Vardi and P. Wolper. The complementation problem for Biichi automata with applications to temporal logic. Theoretical Computer Science 49 (1987), 217-237.
• [15] L. Staiger and K. Wagner. Automatentheoretische und automatenfreie Characterisierungen topologischer Klassen regularer Folgenmengen. Elektronische Informationsverarbeitung und Kybernetik 10 (1974), 379-392.
• [16] L. Staiger. w-Languages. In: Handbook of Formal Languages, vol. 3, Springer, 1997, 339-387.
• [17] W. Thomas. Automata on infinite objects. In: Handbook of Theoretical Computer Science, vol. B, Elsevier 1990, 133-191.
• [18] W. Thomas. Languages, automata and logic. In: Handbook of Formal Languages, vol. 3, Springer 1997, 133-191.
• [19] W. Wadge. Degrees of complexity of subsets of the Baire space. Notices AMS 19 (1972), 714-715.
• [20] W. Wadge. Reducibility and determinateness in the Baire space. PhD thesis, University of California, Berkely, 1984.
• [21] K. Wagner. On w-regular sets. Information and Control 43 (1979), 123-177
• [22] T. Wilke. An algebraic theory for for regular languages of finite and infinite words. Int. J. Alg. Comput., 3 (1993), 447-489.
• [23] G. Wechsung. On the Boolean closure of NP. In: Proceedings of the 5th Int. Conf. on Fundamentals of Computation Theory 1985. Lecture Notes in Computer Science, vol. 199, Springer 1985, 485^493.
• [24] T. Wilke and H. Yoo. Computing the Wadge degree, the Lipschitz degree, and the Rabin index of a regular language of infinite words in polynomial time. In: Proceedings of the 6th TAPSOFTconference 1995. Lecture Notes in Computer Science, vol. 915, Springer 1995, 288-302.
• [25] Q. Yan. Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique. In: Proc. 33rd Int. Colloq. on Automata, Languages and Programming 2006. Lecture Notes in Computer Science, vol. 4052, Springer 2006, 589-600