On Tree-Restricted Regular-Controlled Context-Free Grammars
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F17%3APU126454" target="_blank" >RIV/00216305:26230/17:PU126454 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1080/23799927.2017.1388291" target="_blank" >http://dx.doi.org/10.1080/23799927.2017.1388291</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1080/23799927.2017.1388291" target="_blank" >10.1080/23799927.2017.1388291</a>
Alternative languages
Result language
angličtina
Original language name
On Tree-Restricted Regular-Controlled Context-Free Grammars
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
International Journal of Computer Mathematics: Computer Systems Theory
ISSN
2379-9927
e-ISSN
—
Volume of the periodical
2
Issue of the periodical within the volume
4
Country of publishing house
GB - UNITED KINGDOM
Number of pages
17
Pages from-to
147-163
UT code for WoS article
—
EID of the result in the Scopus database
2-s2.0-85056990677