Czasopismo
2005
|
Vol. 64, nr 1-4
|
307-316
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
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.
Czasopismo
Rocznik
Tom
Strony
307-316
Opis fizyczny
Bibliogr. 24 poz.
Twórcy
autor
- Faculty of Mathematics, Bucharest University, Str. Academiei 14, sector 1, 70109 Bucharest, Romania, vmi@fll.urv.es
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0005-0131