Parsing Local Internal Contextual Languages with Context-Free Choice

• Autorzy: Gramatovici R. , Manea F.
• Języki publikacji: EN

Abstrakty

EN

We extend the result from [8] by giving also a concrete polynomial parsing algorithm for a class of languages generated by a variant of contextual grammars, namely local internal contextual grammars with context-free choice.

Słowa kluczowe

EN

contextual grammars; parsing; polynomial complexity

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

Twórcy

autor

Gramatovici R.

• Faculty of Mathematics, Bucharest University, Str. Academiei 14, 010014 Bucharest, Romania

autor

Manea F.

• Faculty of Mathematics, Bucharest University, Str. Academiei 14, 010014 Bucharest, Romania

Bibliografia

• [1] J. Earley, An efficient context-free parsing algorithm, Comm. of the ACM, 13, 2 (1970), 94–102.
• [2] R. Gramatovici, An efficient parser for a class of contextual languages, Fundamenta Informaticae, 33, 3 (1998), 211–238.
• [3] R. Gramatovici, G. Bel Enguix, Parsing with P automata, in Applications of Membrane Computing (G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez, eds.), Springer-Verlag, Berlin, to appear.
• [4] R. Gramatovici, C.Martín-Vide, 1-Contextual grammars with sorted dependencies, in Proceedings of the 3rd International AMAST Workshop on Algebraic Methods in Language Processing, AMiLP-3, Verona, Italy, 2003, 99–109.
• [5] K. Harbusch, A polynomial parser for contextual grammars with linear, regular and context-free selectors, in Proceedings of MOL6 - Sixth Meeting on the Mathematics of Language, Orlando, Florida/USA, 1999, 323–335.
• [6] K. Harbusch, Parsing contextual grammars with linear, regular and context-free selectors, in Grammars and Automata for String Processing, C. Martin-Vide, V. Mitrana, eds., Taylor & Francis, London, New-York, 2003, 45–54.
• [7] K. Harbusch, An efficient online parser for contextual grammars with at most context-free selectors, in Computational Linguistics and Intelligent Text Processing, 4th International Conference, CICLing 2003, A.F. Gelbukh, ed., LNCS 2588, Springer, Berlin, New York, Tokio, 2003, 168–179.
• [8] L. Ilie, On computational complexity of contextual languages, Theoretical Computer Science, 183 (1997) 33–44.
• [9] L. Ilie, On the computational complexity ofMarcus external contextual languages, Fundamenta Informaticae, 30 (1997) 161–167.
• [10] F. Manea, Contextual grammars and go through automata, Proceedings of the ESSLLI 2003 Student Session, Balder ten Cate, ed., Vienna, Austria, 2003, 159–168.
• [11] S. Marcus, Contextual grammars, Rev. Roum. Math. Pures Appl., 14 (1969), 1525–1534.
• [12] S. Marcus, Contextual grammars and natural languages, chapter 5 in vol. 2 of The Handbook of Formal Languages, G. Rozenberg, A. Salomaa, eds., Springer-Verlag, Berlin, Heidelberg, 1997, 215–235.
• [13] F. Mr´az, M. Pl´atek, M. Proch´azcha, Restarting automata, deleting and Marcus grammars, in Recent Topics in Mathematical and Computational Linguistics, C. Martín-Vide, Gh. Paun, eds., Romanian Academy Publishing House, 2000, 218–233.
• [14] Gh. Păun, Marcus Contextual Grammars, Kluwer, Dordrecht, Boston, London, 1997.
• [15] G. Rozenberg, A. Salomaa, eds., The Handbook of Formal Languages, 3 volumes, Springer-Verlag, Berlin, Heidelberg, 1997.