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:
Publication language:english
Original title:On Tree-Restricted Regular-Controlled Context-Free Grammars
Title (cs):Stromová Omezení Regulárně Řízených Bezkontextových Gramatik
Journal:International Journal of Computer Mathematics: Computer Systems Theory, Vol. 2, No. 4, GB
regular-controlled context-free grammars, restricted derivation trees, contextfreeness of finite index
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.
   author = {Erzs{\'{e}}bet Csuhaj-Varj{\'{u}} and Alexander
	Meduna and Ond{\v{r}}ej Soukup},
   title = {On Tree-Restricted Regular-Controlled Context-Free
   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 = {}

Your IPv4 address:
Switch to https

DNSSEC [dnssec]