Result Details
On Tree-Restricted Regular-Controlled Context-Free Grammars
This paper gives simple tree-based conditions under which
regular-controlled context-free grammars generate context-free languages of finite index, so they cannot even generate all context-free languages. It defines the notion of path-changing derivation step which corresponds to performing two consecutive rewritings of nonterminal symbols present in the different branches of the derivation tree. It proves that if there exists a certain constant that limits the number of path-changing deriva-
tion steps, then, the regular-controlled grammar generates a context-free language of finite index. At the end, we generalize achieved result and provide some open problems for future study.
regular-controlled context-free grammars, restricted derivation trees, contextfreeness of finite index
@article{BUT144477,
author="Alexandr {Meduna} and Ondřej {Soukup} and Erzsébet {Csuhaj-Varjú}",
title="On Tree-Restricted Regular-Controlled Context-Free Grammars",
journal="International Journal of Computer Mathematics- Computer Systems Theory",
year="2017",
volume="2",
number="4",
pages="147--163",
doi="10.1080/23799927.2017.1388291",
issn="2379-9927",
url="http://dx.doi.org/10.1080/23799927.2017.1388291"
}V3C - Visual Computing Competence Center, TAČR, Centra kompetence, TE01020415, start: 2012-05-01, end: 2019-12-31, completed
Výzkum pokročilých metod ICT a jejich aplikace, BUT, Vnitřní projekty VUT, FIT-S-14-2299, start: 2014-01-01, end: 2016-12-31, completed