Tree-controlled grammars with restrictions placed upon cuts and paths
Kybernetika (2012)
- Volume: 48, Issue: 1, page 165-175
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topKoutný, Jiří, and Meduna, Alexander. "Tree-controlled grammars with restrictions placed upon cuts and paths." Kybernetika 48.1 (2012): 165-175. <http://eudml.org/doc/246532>.
@article{Koutný2012,
abstract = {First, this paper discusses tree-controlled grammars with root-to-leaf derivation-tree paths restricted by control languages. It demonstrates that if the control languages are regular, these grammars generate the family of context-free languages. Then, in a similar way, the paper introduces tree-controlled grammars with derivation-tree cuts restricted by control languages. It proves that if the cuts are restricted by regular languages, these grammars generate the family of recursively enumerable languages. In addition, it places a binary-relation-based restriction upon these grammars and demonstrate that this additional restriction does not affect the generative power of these grammars.},
author = {Koutný, Jiří, Meduna, Alexander},
journal = {Kybernetika},
keywords = {context-free grammars; tree-controlled grammars; restricted derivation trees; paths; cuts; language families; context-free grammars; tree-controlled grammars; restricted derivation trees; cuts; paths},
language = {eng},
number = {1},
pages = {165-175},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Tree-controlled grammars with restrictions placed upon cuts and paths},
url = {http://eudml.org/doc/246532},
volume = {48},
year = {2012},
}
TY - JOUR
AU - Koutný, Jiří
AU - Meduna, Alexander
TI - Tree-controlled grammars with restrictions placed upon cuts and paths
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 1
SP - 165
EP - 175
AB - First, this paper discusses tree-controlled grammars with root-to-leaf derivation-tree paths restricted by control languages. It demonstrates that if the control languages are regular, these grammars generate the family of context-free languages. Then, in a similar way, the paper introduces tree-controlled grammars with derivation-tree cuts restricted by control languages. It proves that if the cuts are restricted by regular languages, these grammars generate the family of recursively enumerable languages. In addition, it places a binary-relation-based restriction upon these grammars and demonstrate that this additional restriction does not affect the generative power of these grammars.
LA - eng
KW - context-free grammars; tree-controlled grammars; restricted derivation trees; paths; cuts; language families; context-free grammars; tree-controlled grammars; restricted derivation trees; cuts; paths
UR - http://eudml.org/doc/246532
ER -
References
top- A. V. Aho, J. D. Ullman, The theory of parsing, translation, and compiling., Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972. (1972) MR0408321
- A. Bondy, Graph Theory., Springer, 2010. (2010)
- K. Čulik, H. A. Maurer, 10.1007/BF02252350, Computing 19 (1977), 129-139. (1977) Zbl0363.68108MR0464718DOI10.1007/BF02252350
- J. Dassow, Gh. Păun, Regulated Rewriting in Formal Language Theory., Springer, Berlin 1989. (1989) MR1067543
- J. Dassow, B. Truthe, Subregularly tree controlled grammars and languages., In: Automata and Formal Languages - 12th Int. Conference AFL 2008, Proceedings (E. Csuhaj-Varjú, Z. Ésik, eds.), Balatonfüred, Hungary 2008, pp. 158-169. (2008)
- S. Marcus, C. Martín-Vide, V. Mitrana, Gh. Păun, A new-old class of linguistically motivated regulated grammars., In: Computational Linguistics in the Netherlands 2000, Selected Papers from the Eleventh clin Meeting (W. Daelemans, K. Sima'an, J. Veenstra, J. Zavrel, eds.), Rodopi, Amsterdam 2001, pp. 111-125. (2000) MR1869435
- C. Martín-Vide, V. Mitrana, 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, Edinburgh 2005, pp. 221-232. (2005) MR2153679
- A. Meduna, Automata and Languages: Theory and Applications., Springer Verlag, 2005. (2005) MR1778364
- Gh. Păun, 10.1007/BF02253054, Computing 21 (1979), 3, 213–220. (1979) Zbl0392.68060MR0620209DOI10.1007/BF02253054
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.