Journal article

CSUHAJ-VARJÚ Erzsébet, MEDUNA Alexander and SOUKUP Ondřej. On Tree-Restricted Regular-Controlled Context-Free Grammars. International Journal of Computer Mathematics: Computer Systems Theory. 2017, vol. 2, no. 4, pp. 147-163. ISSN 2379-9927. Available from: http://dx.doi.org/10.1080/23799927.2017.1388291
Publication language:english
Original title:On Tree-Restricted Regular-Controlled Context-Free Grammars
Title (cs):Stromová Omezení Regulárně Řízených Bezkontextových Gramatik
Pages:147-163
Place:GB
Year:2017
URL:http://dx.doi.org/10.1080/23799927.2017.1388291
Journal:International Journal of Computer Mathematics: Computer Systems Theory, Vol. 2, No. 4, GB
ISSN:2379-9927
DOI:10.1080/23799927.2017.1388291
Keywords
regular-controlled context-free grammars, restricted derivation trees, contextfreeness of finite index
Annotation
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.
BibTeX:
@ARTICLE{
   author = {Erzs{\'{e}}bet Csuhaj-Varj{\'{u}} and Alexander
	Meduna and Ond{\v{r}}ej Soukup},
   title = {On Tree-Restricted Regular-Controlled Context-Free
	Grammars},
   pages = {147--163},
   journal = {International Journal of Computer Mathematics: Computer
	Systems Theory},
   volume = {2},
   number = {4},
   year = {2017},
   ISSN = {2379-9927},
   doi = {10.1080/23799927.2017.1388291},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=11533}
}

Your IPv4 address: 34.229.113.106
Switch to https