Detail publikace

On Tree-Restricted Regular-Controlled Context-Free Grammars

MEDUNA, A. SOUKUP, O. CSUHAJ-VARJÚ, E.

Originální název

On Tree-Restricted Regular-Controlled Context-Free Grammars

Typ

článek v časopise ve Scopus, Jsc

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

regular-controlled context-free grammars, restricted derivation trees, contextfreeness of finite index

Autoři

MEDUNA, A.; SOUKUP, O.; CSUHAJ-VARJÚ, E.

Vydáno

27. 10. 2017

ISSN

2379-9927

Periodikum

International Journal of Computer Mathematics: Computer Systems Theory

Ročník

2

Číslo

4

Stát

Spojené království Velké Británie a Severního Irska

Strany od

147

Strany do

163

Strany počet

17

URL

http://dx.doi.org/10.1080/23799927.2017.1388291

BibTex

@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"
}