On Normal Forms and Erasing Rules in Path Controlled Grammars

• Autorzy: Koutnŷ J. , Meduna A.

Identyfikatory

DOI

10.4467/20838476SI.13.001.2086

• Języki publikacji: EN

Abstrakty

EN

This paper discusses path controlled grammars { context-free gram- mars with a root-to-leaf path in their derivation trees restricted by a control language. First, it investigates the impact of erasing rules on the generative power of path controlled grammars. Then, it establishes two Chomsky-like normal forms for path controlled grammars - the first allows unit rules, the second allows just one erasing rule.

Słowa kluczowe

EN

context-free grammars; path controlled grammars; restricted derivation trees; paths; normal forms; erasing rules

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2013
• Tom: Vol. 22
• Strony: 9--18
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Koutnŷ J.

• Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology Božetéchova 2, 612 66 Brno, Czech Republic

autor

Meduna A.

• Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology Božetéchova 2, 612 66 Brno, Czech Republic

Bibliografia

• [1] Bondy A.; Graph Theory, Springer, New York 2010.
• [2] Čermák M., Koutnŷ J., Meduna A.; Parsing based on n-path tree-controlled grammars, Theoretical and Applied Informatics 23, 2011, pp. 213-228.
• [3] Čulik K., Maurer H.A.; Tree controlled grammars, Computing 19, 1977, pp. 129-139.
• [4] Dassow J., Paun Gh.; Regulated Rewriting in Formal Language Theory, Springer, Berlin 1989.
• [5] Dassow J., Truthe B.; Subregularly tree controlled grammars and languages, Automata and Formal Languages - 12th International Conference AFL 2008, 18 Balatonfured, Computer and Automation Research Institute of the Hungarian Academy of Sciences, 2008, pp. 158-169.
• [6] Koutnŷ J., Křivka Z., Meduna A.; Pumping properties of path-restricted tree-controlled languages, 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, 2011, pp. 61-69.
• [7] Koutnŷ J., Meduna A.; Tree-controlled grammars with restrictions placed upon cuts and paths, Kybernetika 48(1), 2012, pp. 165-175.
• [8] Marcus S., Martin-Vide C., Mitrana V., Paun Gh.; A new-old class of linguistically motivated regulated grammars. In: W. Daelemans, K. Sima'an, J. Veenstra, J. Zavrel (eds.); Computational Linguistics in the Netherlands 2000, Selected Papers from the Eleventh CLIN Meeting, Tilburg, Language and Computers -Studies in Practical Linguistics 37, Rodopi 2000, pp. 111-125.
• [9] Martin-Vide C., Mitrana. V.; 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, University of Edinburgh, Edinburgh 2005, pp. 221-232.
• [10] Martin-Vide C., Mitrana V.; Decision problems on path-controlled grammars, IJFCS: International Journal of Foundations of Computer Science 18, 2007.
• [11] Mateescu A., Salomaa A.; Handbook of formal languages, vol. 1, chapter Aspects of classical language theory, Springer-Verlag New York, Inc., New York 1997, pp. 175-251.
• [12] Meduna A.; Automata and Languages: Theory and Applications, Springer, New York 2005.
• [13] Paun Gh.; On the generative capacity of tree controlled grammars, Computing 21(3), 1979, pp. 213-220.
• [14] Salomaa A.; Computation and Automata, vol. 25 of Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge 1985.
• [15] Turaev S., Dassow J., Selamat M.H.; Language classes generated by tree controlled grammars with bounded nonterminal complexity. In: M. Holzer, M. Kutrib, G. Pighizzini (eds.); DCFS, vol. 6808 of Lecture Notes in Computer Science, Springer, New York 2011, pp. 289-300.
• [16] Turaev S., Dassow J., Selamat M.H.; Nonterminal complexity of tree controlled grammars, Theoretical Computer Science 412(41), 2011, pp. 5789-5795.