Detail publikace

On Tree-Restricted Regular-Controlled Context-Free Grammars

MEDUNA, A.; SOUKUP, O.; CSUHAJ-VARJÚ, E. On Tree-Restricted Regular-Controlled Context-Free Grammars. International Journal of Computer Mathematics: Computer Systems Theory, 2017, vol. 2, no. 4, p. 147-163. ISSN: 2379-9927.
Název česky
Stromová Omezení Regulárně Řízených Bezkontextových Gramatik
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Soukup Ondřej, Ing., Ph.D.
Csuhaj-Varjú Erzsébet
URL
Klíčová slova

regulárně řízené bezkontextové gramatiky, omezené derivační stromy, bezkontextovost končného indexu

Abstrakt

Článek představuje jednoduché podmínky založené na derivačních stromech, při jejichž splnění regulárně řízené bezkontextové gramatiky generují bezkontextové jazyky konečného indexu, a tedy nemohou generovat ani všechny bezkontextové jazyky. Dále je definován pojem tzv. path-changing derivačního kroku, který označuje dva po sobě jdoucí přepisy neterminálních symbolů ve dvou různých větvích derivačního stromu. Je dokázáno, že pokud existuje konstanta omezující počet path-changing derivačních kroků, regulárně řízená gramatika generuje bezkontextový jazyk konečného indexu. Dosažená výsledek je nakonec zobecněno a je také položeno několik otevřených problémů.

Rok
2017
Strany
147–163
Časopis
International Journal of Computer Mathematics: Computer Systems Theory, roč. 2, č. 4, ISSN 2379-9927
DOI
10.1080/23799927.2017.1388291
EID Scopus
2-s2.0-85056990677
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"
}
Nahoru