Detail publikace

Simple Matrix Grammars and Their Leftmost Variants

MEDUNA Alexander a SOUKUP Ondřej. Simple Matrix Grammars and Their Leftmost Variants. International Journal of Foundations of Computer Science, roč. 27, č. 3, 2016, s. 359-373. ISSN 0129-0541. Dostupné z: http://www.worldscientific.com/doi/10.1142/S0129054116400141
Název česky
Jednoduché Maticové Gramatiky a jejich Nejlevější Varianty
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Abstrakt

Na jednoduché maticové gramatiky můžeme nahlížet jako na posloupnosti bezkontextových gramatik nazývané komponenty, které pracují paralelně. Článek demonstruje, že dvoukomponentové maticové gramatiky pokrývají svou výpočetní silou celou rodinu maticových gramatik. Následně jsou představeny tři módy nejlevějších derivací a dokázáno, že rodina jednoduchých maticových gramatik pracujících ve dvou z těchto tří módů je výpočetně úplná - ekvivalentní k Turingovým strojům. V souvislosti s historií zkoumání jednoduchých maticových gramatik navíc článek navazuje na předchozí tvrzení, z nichž některá opravuje.

Rok
2016
Strany
359-373
Časopis
International Journal of Foundations of Computer Science, roč. 27, č. 3, ISSN 0129-0541
DOI
UT WoS
000378637600005
EID Scopus
BibTeX
@ARTICLE{FITPUB10751,
   author = "Alexander Meduna and Ond\v{r}ej Soukup",
   title = "Simple Matrix Grammars and Their Leftmost Variants",
   pages = "359--373",
   journal = "International Journal of Foundations of Computer Science",
   volume = 27,
   number = 3,
   year = 2016,
   ISSN = "0129-0541",
   doi = "10.1142/S0129054116400141",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10751"
}
Nahoru