On Normal Forms and Erasing Rules in Path Controlled Grammars
cytuj
pobierz pliki
RIS BIB ENDNOTEChoose 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 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.
Bondy A.; Graph Theory, Springer, New York 2010.
Cermak M., Koutny J., Meduna A.; Parsing based on n-path tree-controlled grammars, Theoretical and Applied Informatics 23, 2011, pp. 213{228.
Culik K., Maurer H.A.; Tree controlled grammars, Computing 19, 1977, pp. 129{139.
Dassow J., Paun Gh.; Regulated Rewriting in Formal Language Theory, Springer, Berlin 1989.
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.
Koutny J., Krivka 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.
Koutny J., Meduna A.; Tree-controlled grammars with restrictions placed upon cuts and paths, Kybernetika 48(1), 2012, pp. 165{175.
Marcus S., Martn-Vide C., Mitrana V., Paun Gh.; A new-old class of linguisti- cally 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.
Martn-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.
Martin-Vide C., Mitrana V.; Decision problems on path-controlled grammars, IJFCS: International Journal of Foundations of Computer Science 18, 2007.
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.
Meduna A.; Automata and Languages: Theory and Applications, Springer, New York 2005.
Paun Gh.; On the generative capacity of tree controlled grammars, Computing 21(3), 1979, pp. 213{220.
Salomaa A.; Computation and Automata, vol. 25 of Encyclopedia of Mathemat- ics and Its Applications, Cambridge University Press, Cambridge 1985.
Turaev S., Dassow J., Selamat M.H.; Language classes generated by tree con- trolled 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.
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 article
Titles:
On Normal Forms and Erasing Rules in Path Controlled Grammars
On Normal Forms and Erasing Rules in Path Controlled Grammars
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
Published at: 06.06.2014
Article status: Open
Licence: None
Percentage share of authors:
Article corrections:
-Publication languages:
EnglishView count: 3563
Number of downloads: 1734