Prof. RNDr. Alexander Meduna, CSc.

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. 2017, roč. 2, č. 4, s. 147-163. ISSN 2379-9927. Dostupné z: http://dx.doi.org/10.1080/23799927.2017.1388291
Jazyk publikace:angličtina
Název publikace:On Tree-Restricted Regular-Controlled Context-Free Grammars
Název (cs):Stromová Omezení Regulárně Řízených Bezkontextových Gramatik
Strany:147-163
Místo vydání:GB
Rok:2017
URL:http://dx.doi.org/10.1080/23799927.2017.1388291
Časopis:International Journal of Computer Mathematics: Computer Systems Theory, roč. 2, č. 4, GB
ISSN:2379-9927
DOI:10.1080/23799927.2017.1388291
Klíčová slova
regulárně řízené bezkontextové gramatiky, omezené derivační stromy, bezkontextovost končného indexu
Anotace
Č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ů.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=11533}
}

Vaše IPv4 adresa: 34.238.189.171
Přepnout na https