Publication Details
Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
context-free grammars, tree-controlled grammars, restricted derivation trees, paths, cuts, language families
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.
@article{BUT91444,
author="Jiří {Koutný} and Alexandr {Meduna}",
title="Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths",
journal="Kybernetika",
year="2012",
volume="48",
number="1",
pages="165--175",
issn="0023-5954",
url="http://www.kybernetika.cz/content/2012/1/165"
}