Marcus External Contextual Grammars: From One to Many Dimensions

• Autorzy: Mitrana V.
• Języki publikacji: EN

Abstrakty

EN

This work is a continuation of [9]. We extend the multi-dimensional external contextual grammars introduced in the aforementioned work with the possibility of adjoining contexts in a selective way. An investigation of some mathematical properties (computational power and recognition complexity) of these new variants of contextual grammars is done via a constant comparison with the corresponding properties of classic Marcus external contextual grammars with or without choice.

Słowa kluczowe

EN

external contextual grammars; multi-dimensional external contextual grammars; range concatenation grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 307--316
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Mitrana V.

• Faculty of Mathematics, Bucharest University, Str. Academiei 14, sector 1, 70109 Bucharest, Romania,

Bibliografia

• [1] P. Boullier, From contextual grammars to range concatenation grammars, Proc. 6th Conference on Formal Grammar and 7th Conference on Mathematics of Languages FG/MOL’01, ENCS 53, 2001.
• [2] P. Boullier, Range concatenation grammars, Proc. 6th InternationalWorkshop on Parsing Technologies IWPT 2000, 53–64.
• [3] P. Boullier, A cubic time extension of context-free grammars, Grammars, 3 (2000), 111–131.
• [4] G. Gazdar, G.K. Pullum, Computationally relevant properties of natural languages and their grammars, New Generation Computing, 3 (1985), 273–306.
• [5] O. Ibarra, Simple matrix languages, Information and Control, 17 (1970), 359–394.
• [6] L. Ilie, On the computational complexity of contextual languages, Theoretical Computer Sci. 183 (1997), 33–44.
• [7] A.K. Joshi, How much context-sensitivity is required to provide reasonable structural descriptions: tree adjoining grammars, in: Natural Language Parsing: Psychological, Computational and Theoretical Perspectives (D. Dowty, L. Karttunen, A. Zwicky, Eds.), Cambridge University Press, Cambridge, 1985, 206–250.
• [8] A.K. Joshi, Y. Schabes, Tree-adjoining grammars, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), vol. 3, Springer Verlag, Berlin, 1997, 69–123.
• [9] M. Kudlek, C. Martín-Vide, A. Mateescu, V. Mitrana, Contexts and the concept of mild context-sensitivity, Linguistics and Philosophy, 26(6) (2003), 703–725.
• [10] A.Manaster Ramer, Some uses and abuses of mathematics in linguistics, in: Issues in Mathematical Linguistics (C. Mart´ın-Vide, Ed.), John Benjamins, Amsterdam, 1999, 73–130.
• [11] S. Marcus, Algebraic Linguistics. Analitical Models, Academic Press, 1967.
• [12] S. Marcus, Contextual grammars, Rev. Roum.Math. Pures Appl., 14, 10 (1969), 1525–1534.
• [13] S.Marcus, Contextual grammars and natural languages, in: Handbook of Formal Languages, (G. Rozenberg, A. Salomaa, Eds.) vol. 2, Springer, Berlin, 1997, 215–236.
• [14] B.H. Partee, A. ter Meulen, R.E. Wall, Mathematical Methods in Linguistics, Kluwer, Academic Publishers, 1990.
• [15] Gh. Păun, On contextual grammars, Stud. Cerc. Matem. 26 (1974), 1111–1129.
• [16] Gh. Păun, G. Rozenberg, A. Salomaa, Contextual grammars: erasing, determinism, one-sided contexts, in: Developments in Language Theory (G. Rozenberg, A. Salomaa, Eds.), World Sci. Publ., Singapore, 1994, 370–388.
• [17] Gh. Păun, Marcus Contextual Grammars, Studies in Linguistics and Philosophy vol. 67, Kluwer Academic Publishers, 1997.
• [18] G.K. Pullum, On two recent attempts to show that English is not a CFL, Computational Linguistics, 10 (1985), 182 – 186.
• [19] G.K. Pullum, G. Gazdar, Natural languages and context-free languages, Linguistics and Philosophy, 4 (1982), 471 – 504.
• [20] W.C. Rounds, A.Manaster Ramer, J. Friedman, Finding natural languages a home in formal language theory, in: Mathematics of Language (A. Manaster Ramer Ed.), John Benjamins, Amsterdam, 1987, 349–360.
• [21] G. Rozenberg, A. Salomaa, Eds., Handbook of Formal Languages, 3 vols. Springer Verlag, Berlin, 1997.
• [22] W.J. Savitch, E. Bach, W. Marsh, G. Safran-Naveh, Eds., The Formal Complexity of Natural Language, Reidel, Dordrecht, 1987.
• [23] S.M. Shieber, Evidence against the context-freeness of natural languages, Linguistics and Philosophy, 8 (1985).
• [24] D. Weir, Characterizing Mildly Context-sensitive Grammar Formalisms, PhD dissertation, University of Pennsylvania, 1988.