Geodesic
Tree-controlled grammars with restrictions placed upon cuts and paths
Kybernetika, Tome 48 (2012) no. 1, pp. 165-175

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {48},
     number = {1},
     year = {2012},
     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
PB  - mathdoc
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
%I mathdoc
%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/