Geodesic
Tree-controlled grammars with restrictions placed upon cuts and paths
Kybernetika, Tome 48 (2012) no. 1, pp. 165-175 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 68Q42
Keywords: context-free grammars; tree-controlled grammars; restricted derivation trees; paths; cuts; language families 
@article{KYB_2012_48_1_a9,
     author = {Koutn\'y, Ji\v{r}{\'\i} and Meduna, Alexander},
     title = {Tree-controlled grammars with restrictions placed upon cuts and paths},
     journal = {Kybernetika},
     pages = {165--175},
     year = {2012},
     volume = {48},
     number = {1},
     mrnumber = {2932934},
     zbl = {1260.68195},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012_48_1_a9/}
}
TY  - JOUR
AU  - Koutný, Jiří
AU  - Meduna, Alexander
TI  - Tree-controlled grammars with restrictions placed upon cuts and paths
JO  - Kybernetika
PY  - 2012
SP  - 165
EP  - 175
VL  - 48
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/KYB_2012_48_1_a9/
LA  - en
ID  - KYB_2012_48_1_a9
ER  - 
%0 Journal Article
%A Koutný, Jiří
%A Meduna, Alexander
%T Tree-controlled grammars with restrictions placed upon cuts and paths
%J Kybernetika
%D 2012
%P 165-175
%V 48
%N 1
%U http://geodesic.mathdoc.fr/item/KYB_2012_48_1_a9/
%G en
%F KYB_2012_48_1_a9
Koutný, Jiří; Meduna, Alexander. Tree-controlled grammars with restrictions placed upon cuts and paths. Kybernetika, Tome 48 (2012) no. 1, pp. 165-175. http://geodesic.mathdoc.fr/item/KYB_2012_48_1_a9/

[1] A. V. Aho, J. D. Ullman: The theory of parsing, translation, and compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972. | MR

[2] A. Bondy: Graph Theory. Springer, 2010.

[3] K. Čulik, H. A. Maurer: Tree controlled grammars. Computing 19 (1977), 129-139. | DOI | MR | Zbl

[4] J. Dassow, Gh. Păun: Regulated Rewriting in Formal Language Theory. Springer, Berlin 1989. | MR

[5] 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.

[6] 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. | MR

[7] 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. | MR

[8] A. Meduna: Automata and Languages: Theory and Applications. Springer Verlag, 2005. | MR

[9] Gh. Păun: On the generative capacity of tree controlled grammars. Computing 21 (1979), 3, 213–220. | DOI | MR | Zbl