Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
next last
cannonical link button


Fundamenta Informaticae

Tytuł artykułu

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

Autorzy Chen, Z. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
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  
Wydawca IOS Press
Czasopismo Fundamenta Informaticae
Rocznik 2011
Tom Vol. 111, nr 2
Strony 119--145
Opis fizyczny Bibliogr. 15 poz.
autor Chen, Z.
  • College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, 29 Yudao Street, 210016 Nanjing, Jiangsu, China,
[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.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BUS8-0021-0001