On Normal Forms and Erasing Rules in Path Controlled Grammars
Choose format
RIS BIB ENDNOTEOn Normal Forms and Erasing Rules in Path Controlled Grammars
Publication date: 06.06.2014
Schedae Informaticae, 2013, Volume 22, pp. 9-18
https://doi.org/10.4467/20838476SI.13.001.2086Authors
On Normal Forms and Erasing Rules in Path Controlled Grammars
This paper discusses path controlled grammars—context-free grammars 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.
[1] Bondy A.; Graph Theory, Springer, New York 2010.
[2] Cˇerm´ak M., Koutn_y J., Meduna A.; Parsing based on n-path tree-controlled grammars, Theoretical and Applied Informatics 23, 2011, pp. 213–228.
[3] Cˇulik ., Maurer H.A.; Tree controlled grammars, Computing 19, 1977, pp. 129–139.
[4] Dassow J., P_aun 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, Balatonfured, Computer and Automation Research Institute of the Hungarian Academy of Sciences, 2008, pp. 158–169.
[6] Koutn_y J., K_rivka 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_y J., Meduna A.; Tree-controlled grammars with restrictions placed upon cuts and paths, Kybernetika 48(1), 2012, pp. 165–175.
[8] Marcus S., Mart__n-Vide C., Mitrana V., P_aun 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] Mart´ın-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] P_aun 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.
Information: Schedae Informaticae, 2013, Volume 22, pp. 9-18
Article type: Original scientific article
Published at: 06.06.2014
Article status: Open
Licence: None
Percentage share of authors:
Article corrections:
-Publication languages:
EnglishView count: 4039
Number of downloads: 2112