Parsing based on n-path tree - controlled grammars

• Autorzy: Čermák M. , Koutný J. , Meduna A.
• Języki publikacji: EN

Abstrakty

EN

This paper discusses recently introduced kind of linguistically motivated restriction placed on tree-controlled grammars-context-free grammars with some root-to-leaf paths in their derivation trees restricted by a control language. We deal with restrictions placed on n greater-than or equal to 1 paths controlled by a deterministic context-free language, and we recall several basic properties of such a rewriting system. Then, we study the possibilities of corresponding parsing methods working in polynomial time and demonstrate that some non-context-free languages can be generated by this regulated rewriting model. Furthermore, we illustrate the syntax analysis of LL grammars with controlled paths. Finally, we briefly discuss how to base parsing methods on bottom-up syntax-analysis.

Słowa kluczowe

EN

regulated rewriting; derivation tree; tree-controlled grammars; path-controlled grammars; parsing; n-path tree-controlled grammars

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2011
• Tom: Vol. 23, No. 3-4
• Strony: 213--228
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Čermák M.

autor

Koutný J.

autor

Meduna A.

• Formal Model Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology Božetechova 2, 612 66 Brno, Czech Republic,

Bibliografia

• 1. A. Bondy: Graph Theory. Springer, 2010.
• 2. M. Cermák, A. Meduna: N-accepting restricted pushdown automata systems. In 13th International Conference on Automata and Formal Languages, pages 168- 183. Computer and Automation Research Institute, Hungarian Academy of Sci-ences, 2011.
• 3. K. Culik, H. A. Maurer: Tree controlled grammars, Computing, 19:129-139, 1977.
• 4. J. Dassow, Gh. Paun, and A. Salomaa: ˘ Grammars with controlled derivations. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Volume II, pages 101-154. Berlin: Springer, 1997.
• 5. J. Dassow, Gh. Paun: ˘ Regulated Rewriting in Formal Language Theory. aun. Springer,Berlin, 1989.228
• 6. J. Dassow, B. Truthe: Subregularly tree controlled grammars and languages. In Automata and Fromal Languages – 12th International Conference AFL 2008, Balatonfured, pages 158-169. Computer and Automation Research Institute of the Hungarian Academy of Sciences, 2008.
• 7. J. Higginbotham: English is not a context-free language. Linguistic Inquiry, 15(2):225-234, 1984.
• 8. A. K. Joshi: Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions. Technical Report MS-CIS-85-23, University of Pennsylvania.
• 9. J. Koutný: Syntax analysis of tree-controlled languages. In Proceedings of the 17th Conference and Competition STUDENT EEICT 2011 Volume 3, page 5. Faculty of Information Technology BUT, 2011.
• 10. J. Koutný, Z. Kˇrivka, A. Meduna: Pumping properties of path-restricted tree-controlled languages. In 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, pages 61-69. Brno University of Technology, 2011.
• 11. J. Koutný, A. Meduna: Tree-controlled grammars with restrictions placed upon cuts and paths. Kybernetika, 2011, in press.
• 12. S. Marcus, C. Martín-Vide, V. Mitrana, Gh. Paun: ˘ A new-old class of lin aun. Guistically motivated regulated grammars. In Walter Daelemans, Khalil Sima’an, Jorn Veenstra,Jakub Zavrel (Eds.): Computational Linguistics in the Netherlands 2000, Selected Papers from the Eleventh CLIN Meeting, Tilburg, pages 111-125. Language and Computers-Studies in Practical Linguistics 37 Rodopi 2000, 2000.
• 13. C. Martín-Vide, V. Mitrana: Further properties of path-controlled grammars. In Proceedings of FG-MoL 2005: The 10th Conference on Formal Grammar and The 9th Meeting on Mathematics of Language, pages 221-232. University of Edinburgh, Edinburgh, 2005.
• 14. A. Meduna: Automata and Languages: Theory and Applications. Springer, 2005.
• 15. Gh. Paun: ˘ On the generative capacity of tree controlled grammars. Computing,aun.21(3):213-220, 1979.
• 16. E. L. Post: A variant of a recursively unsolvable problem. Bulletion of the American Mathematical Society, 52:264-268, 1946.
• 17. G. K. Pullum: On two recent attempts to show that english is not a CFL. Computational Linguistics, 10(3-4):182-186, 1984.
• 18. G. K. Pullum, G. Gazdar: Natural languages and context-free languages. Linguistics and Philosophy, 4(4):471-504, 1982.
• 19. Rosenkrantz and Stearns: Properties of deterministic top down grammars. In STOC: ACM Symposium on Theory of Computing (STOC), 1969.
• 20.S. Shieber: Evidence against the context-freeness of natural language. Linguistics and Philosophy, 8:333-343, 1985.