FAQ
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
Contact with author
All publications →
Alexander Meduna
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
Contact with author
All publications →

Download full text

Titles

On Normal Forms and Erasing Rules in Path Controlled Grammars

Abstract

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.

References

Download references

[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

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

Article type: Original article

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

On Normal Forms and Erasing Rules in Path Controlled Grammars

cytuj

pobierz pliki

RIS BIB ENDNOTE