FAQ

Schedae Informaticae

logo of Jagiellonian University in Krakow

On 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.2086

Authors

,
Jiŕí Koutnŷ
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
All publications →
Alexander Meduna
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
All publications →

Abstract

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.

References

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

Information: Schedae Informaticae, 2013, pp. 9 - 18

Article type: Original research article

Titles:

English:

On Normal Forms and Erasing Rules in Path Controlled Grammars

Authors

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:

Jiŕí Koutnŷ (Author) - 50%
Alexander Meduna (Author) - 50%

Article corrections:

-

Publication languages:

English

View count: 23

Number of downloads: 22