On Insertion Grammars with Maximum Parallel Derivation

• Autorzy: Dinu, L.P.
• Języki publikacji: EN

Abstrakty

EN

In this paper we investigate insertion grammars and explore their capacity to generate words parallelly by introducing parallel derivation (where more than one rule can be applied to the string in parallel) and maximum parallel derivation (where as many rules as possible are applied to the string in parallel). We compare the generative power of these grammars with context sensitive and context free grammars and with different variants of contextual grammars. We apply these grammars to syllabification in Romanian and provide arguments that they can also be used in a cognitive perspective.

Słowa kluczowe

EN

insertion grammars; parallel derivation; contextual grammars; parallel syllabification

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 93, nr 4
• Strony: 357-369
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Dinu, L.P.

• University of Bucharest, Faculty of Mathematics and Computer Science, Centre for Computational Linguistics, Academiei 14, 010014 Bucharest, Romania,

Bibliografia

• [1] Bird, S. and T. M. Ellison. One-level phonology. Autosegmental representations and rules as finite automata. Computational Linguistics 20, 55-90,1994.
• [2] Chomsky, N. Syntactic Structures, Mouton, The Hague, 1957.
• [3] A. Dinu, L.P. Dinu. A parallel approach to syllabification. In A. Gelbukh (Ed.): CICLing 2005. LNCS 3406, 83-87,2005.
• 141 Dinu, L.P. An approach to syllables via some extensions of Marcus contextual grammars. Grammars, 6(1), 2003,1-12.
• [5] Galiukschov, B.S. Semicontextual grammars (in Russian), Mat. logica i mat. ling., Kalinin Univ. 38-50,1981.
• [6] Joshi, A.K., L.S. Levy, M. Takahashi. Tree adjoining grammars. J. Computer System Sci., 19,136-163,1975.
• [7] Kaplan, R.M. and M. Kay. Regular models of phonological rule systems. Computational Linguistics, 20(3), 331-379, 1994.
• [8] Kari, L., Gh. Păun, G. Thierrin, S. Yu. At the crossroads of DNA computing and formal languages: characterizing RE using insertiondeletion systems, Proc. the Third DIMACS Workshop on DNA Based Computing, Philadelphia, 1997, pp. 318-333.
• [9J Koskenniemi, K. Two-level morphology: A general computational model for word-form recognition and production. Doctoral dissertation, University of Helsinki, 1983.
• [10] Levelt, W.J.M. and L. Wheeldon. Do speakers have access to a mental syllabary? Cognition 50, 239-269, 1994.
• [11] Levelt, W.J.M. and P. Indefrey. The Speaking Mind/Brain: Where do spoken words come from? In Image, Language, Brain, eds. A. Marantz, Y. Miyashita and W. O'Neil, pp. 77-94. Cambridge, MA: MIT Press, 2001.
• [12] Marcus, S. Contextual grammars. Rev Roum. Math. Pures Appl. 14, 10, 69-74, 1969.
• [13] Marcus, S., C. Martin-Vide and Gh. Păun. Contextual Grammars as Generative Models of Natural Languages. Computational Linguistics 24, 2, 245-265, 1998.
• [14] Margenstern, M., Gh. Păun, Y. Rogozhind, S. Verlana. Context-free insertiondeletion systems. Theoretical Computer Science 330, 339-348, 2005.
• [15] Martin-Vide, C. Natural Computation for Natural Languages. Fundamenta Informaticae 31, 117-124, 1997.
• [16] Martin-Vide, C, Gh. Păun, A. Salomaa. Characterization of RE Languages by Means of Insertion Grammars. TUCS Technical Report No 45, 1996.
• [17] Mitchel, T. Machine Learning. McGraw-Hill, Singapore, 1997.
• [18] Miiller, K. Probabilistic Syllable Modeling Using Unsupervised and Supervised Learning Methods PhD Thesis, Univ. of Stuttgart, Institute of Natural Language Processing, AIMS 2002, vol. 8, no.3, 2002.
• [19] Păun, Gh. Marcus Contextual Grammar. Kluwer Academic Publishers, Studies in Linguistics and Philosophy, Dordrecht-Boston-London, 1997.
• [20] Rozenberg, G. and A. Salomaa (eds.) The Handbook of Formal Languages, Springer-Verlag Berlin Heidelberg, 1997.