Faculty of Information Technology, BUT

Publication Details

On Tree-Restricted Regular-Controlled Context-Free Grammars

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, vol. 2, no. 4, pp. 147-163. ISSN 2379-9927. Available from: http://dx.doi.org/10.1080/23799927.2017.1388291
Czech title
Stromová Omezení Regulárně Řízených Bezkontextových Gramatik
Type
journal article
Language
english
Authors
Csuhaj-Varjú Erzsébet, D.Sc. ( unknown)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Soukup Ondřej, Ing. (DIFS FIT BUT)
URL
Keywords
regular-controlled context-free grammars, restricted derivation trees, contextfreeness of finite index
Abstract
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.
Published
2017
Pages
147-163
Journal
International Journal of Computer Mathematics: Computer Systems Theory, vol. 2, no. 4, ISSN 2379-9927
Publisher
Taylor & Francis Informa plc
DOI
BibTeX
@ARTICLE{FITPUB11533,
   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 = "https://www.fit.vut.cz/research/publication/11533"
}
Back to top