Syllabic Languages and Go-through Automata

• Autorzy: Dinu L.P. , Gramatovici R. , Manea F.

Identyfikatory

DOI

10.3233/FI-2014-1022

• Języki publikacji: EN

Abstrakty

EN

In this paper we define a new class of contextual grammars and study how the languages generated by such grammars can be accepted by go-through automata. The newly introduced class of grammars is a generalization of the formalism previously used to describe the linguistic process of syllabification. Go-through automata which are used here to recognize, and also parse, the languages generated by this new class of grammars are generalizations of push-down automata in the area of context-sensitivity; they have been proved to be an efficient tool for the recognition of languages generated by contextual grammars. The main results of the paper show how the newly introduced generative model is related with other classes of Marcus contextual languages, and how syllabic languages are recognized and parsed using go-through automata.

Słowa kluczowe

EN

contextual grammars; syllabic languages; go-through automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 3-4
• Strony: 409--424
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Dinu L.P.

• University of Bucharest, Faculty of Mathematics and Computer Science, Academiei 14, 010014 Bucharest, Romania

autor

Gramatovici R.

• University of Bucharest, Faculty of Mathematics and Computer Science, Academiei 14, 010014 Bucharest, Romania

autor

Manea F.

• University of Bucharest, Faculty of Mathematics and Computer Science, Academiei 14, 010014 Bucharest, Romania

Bibliografia

• [1] L. P. Dinu, An approach to syllables via some extensions of Marcus contextual grammars, Grammars, 6(1), 1-12, 2003.
• [2] R. Gramatovici, An efficient parser for a class of contextual languages, Fundamenta Informaticae, 33, 211-238, 1998.
• [3] R. Gramatovici, On the Recognizing Power of Non-Expansive Go-Through Automata, Analele Universitătii Bucures¸ti, LII(1), 45-54, 2003.
• [4] R. Gramatovici, Bounded Deterministic Go-Through Automata, Rom. J. Inform. Sc. Tech., 6(1-2), 153-164, 2003.
• [5] R. Gramatovici, C. Martın-Vide, 1-Contextual Grammars with Sorted Dependencies. In Proceedings of 3rd International AMAST Workshop on Algebraic Methods in Language Processing, AMiLP-3, Verona, Italy, 99-109, 2003.
• [6] J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
• [7] P. Jančar, F. Mráz, M. Plátek, J. Vogel, Restarting Automata, in Proceedings of FCT 1995, LNCS 965, 283-292, 1995.
• [8] M. Kappes, On the Generative Capacity of Bracketed Contextual Grammars, Grammars, 1(2), 91-101, 1998.
• [9] M. Kappes, Multi-Bracketed Contextual Grammars, Journal of Automata, Languages and Combinatorics, 3(2), 85-103, 1998.
• [10] F. Manea, Contextual Grammars and Go Through Automata, in Balder ten Cate, ed., Proceedings of the 8th ESSLLI Student Session, Vienna, Austria, 159-168, 2003.
• [11] S. Marcus, Contextual grammars. Rev Roum. Math. Pures Appl. 14, 69-74, 1969.
• [12] S. Marcus, Contextual grammars and natural languages. In Rozenberg, G. and A. Salomaa (eds.) The Handbook of Formal Languages, Springer-Verlag Berlin Heidelberg, vol. 2, 215-235, 1997.
• [13] S. Marcus, C. Mart´ın-Vide, Gh. P˘aun, Contextual Grammars as Generative Models of Natural Languages, Computational Linguistics 24, 2, 245-265, 1998.
• [14] C. Martın-Vide, Natural Computation for Natural Languages. Fundamenta Informaticae 31, 117-124, 1997.
• [15] C. Martın-Vide, G. Păun, Structured contextual grammars, Grammars, 1(1), 33-55 , 1998.
• [16] A. Meduna, Deep Pushdown Automata, Acta Informatica 42(8–9), 541–552, 2006.
• [17] F. Mráz, M. Plátek, M. Procházcha, Restarting automata, deleting and Marcus grammars, in C. Martın-Vide, Gh. Păun (eds.) Recent Topics in Mathematical and Computational Linguistics, Romanian Academy Publishing House, Bucharest, Romania, 218-233, 2000.
• [18] G. Păun, Marcus Contextual Grammar, Kluwer Academic Publishers, Studies in Linguistics and Philosophy, Dordrecht-Boston-London, 1997.