On the Generative Power of !-Grammars and ω-Automata

• Autorzy: Chen, Z.
• Języki publikacji: EN

Abstrakty

EN

An ω-grammar is a formal grammar used to generate ω-words (i.e. infinite length words), while an ω-automaton is an automaton used to recognize ω-words. This paper gives clean and uniform definitions for ω-grammars and ω-automata, provides a systematic study of the generative power of ω-grammars with respect to ω-automata, and presents a complete set of results for various types of ω-grammars and acceptance modes. We use the tuple (σ, ρ, π) to denote various acceptance modes, where σ denotes that some designated elements should appear at least once or infinitely often, ρ denotes some binary relation between two sets, and π denotes normal or leftmost derivations. Technically, we propose (σ, ρ, π)-accepting ω-grammars, and systematically study their relative generative power with respect to (ρ,π)-accepting ω-automata. We show how to construct some special forms of ω-grammars, such as ε-production-free ω-grammars. We study the equivalence or inclusion relations between ω-grammars and ω-automata by establishing the translation techniques. In particular, we show that, for some acceptance modes, the generative power of ω-CFG is strictly weaker than ω-PDA, and the generative power of ω-CSG is equal to ω-TM (rather than linearbounded ω-automata-like devices). Furthermore, we raise some remaining open problems for two of the acceptance modes.

Słowa kluczowe

EN

omega-automaton; omega-grammar; omega-language; generative power

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 2
• Strony: 119-145
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Chen, Z.

• College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, 29 Yudao Street, 210016 Nanjing, Jiangsu, China,

Bibliografia

• [1] Büchi, J. R.: On a Decision Method in Restricted Second Order Arithmetic, Proceedings of the International Congress on Logic, Methodology, and Philosophy of Science, Stanford University Press, 1960, 1-11.
• [2] Büchi, J. R.: Decision Methods in the Theory of Ordinals, Bulletin of the American Mathematical Society, 71(5), 1965, 767-770.
• [3] Büchi, J. R., Landweber, L. H.: Definability in theMonadic Second-Order Theory of Successor, The Journal of Symbolic Logic, 34(2), 1969, 166-170.
• [4] Choueka, Y.: Theories of Automata on ω-Tapes: A Simplified Approach, Journal of Computer and System Sciences, 8(2), 1974, 117-141.
• [5] Cohen, R. S., Gold, A. Y.: Theory of ω-Languages. I: Characterizations of ω-Context-Free Languages, Journal of Computer and System Sciences, 15(2), 1977, 169-184.
• [6] Cohen, R. S., Gold, A. Y.: Theory of ω-Languages. II: A Study of VariousModels of ω-Type Generation and Recognition, Journal of Computer and System Sciences, 15(2), 1977, 185-208.
• [7] Cohen, R. S., Gold, A. Y.: ω-Computations on Turing Machines, Theoretical Computer Science, 6, 1978, 1-23.
• [8] Elgot, C. C., Rabin, M. O.: Decidability and Undecidability of Extensions of Second (First) Order Theory of (Generalized) Successor, The Journal of Symbolic Logic, 31(2), 1966, 169-181.
• [9] Engelfriet, J., Hoogeboom, H. J.: X-Automata on ω-Words, Theoretical Computer Science, 110(1), 1993, 1-51.
• [10] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading MA, 1979.
• [11] Landweber, L. H.: Decision Problems for ω-Automata, Mathematical Systems Theory, 3(4), 1969, 376-384.
• [12] McNaughton, R.: Testing and Generating Infinite Sequences by a Finite Automaton, Information and Control, 9(5), 1966, 521-530.
• [13] Rabin, M. O.: Decidability of Second Order Theories and Automata on Infinite Trees, Transactions of the American Mathematical Society, 141(5), 1969, 1-35.
• [14] Thomas, W.: Automata on Infinite Objects, Handbook of Theoretical Computer Science (vol. B): Formal Models and Semantics, MIT Press, Cambridge,MA, USA, 1991, 133-191.
• [15] Thomas, W.: Languages, Automata, and Logic, Handbook of Formal Languages, III, Springer, 1997, 389-455.