Detail publikace

On Tree-Restricted Regular-Controlled Context-Free Grammars

CSUHAJ-VARJÚ Erzsébet, MEDUNA Alexander a SOUKUP Ondřej. On Tree-Restricted Regular-Controlled Context-Free Grammars. International Journal of Computer Mathematics: Computer Systems Theory, roč. 2, č. 4, 2017, s. 147-163. ISSN 2379-9927. Dostupné z: http://dx.doi.org/10.1080/23799927.2017.1388291
Název česky
Stromová Omezení Regulárně Řízených Bezkontextových Gramatik
Typ
článek v časopise
Jazyk
angličtina
Autoři
Csuhaj-Varjú Erzsébet, D.Sc. ( neznámá)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Soukup Ondřej, Ing. (UIFS FIT VUT)
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
Vydavatel
Taylor & Francis Informa plc
DOI
10.1080/23799927.2017.1388291
EID Scopus
2-s2.0-85056990677
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"
}
Nahoru