Publication Details

Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths

KOUTNÝ Jiří and MEDUNA Alexander. Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths. Kybernetika, vol. 48, no. 1, 2012, pp. 165-175. ISSN 0023-5954. Available from: http://www.kybernetika.cz/content/2012/1/165
Czech title
Stomem řízené gramatiky s omezeními na řezy a cesty
Type
journal article
Language
english
Authors
Koutný Jiří, Ing. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
URL
Keywords

context-free grammars, tree-controlled grammars, restricted derivation trees, paths, cuts, language families 

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 adi- tional restriction does not affect the generative power of these grammars.

Published
2012
Pages
165-175
Journal
Kybernetika, vol. 48, no. 1, ISSN 0023-5954
EID Scopus
2-s2.0-84858040799
BibTeX 
@ARTICLE{FITPUB9699,
   author = "Ji\v{r}\'{i} Koutn\'{y} and Alexander Meduna",
   title = "Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths",
   pages = "165--175",
   journal = "Kybernetika",
   volume = 48,
   number = 1,
   year = 2012,
   ISSN = "0023-5954",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9699"
}
Back to top