Článek v časopise

MEDUNA Alexander a SOUKUP Ondřej. Simple Matrix Grammars and Their Leftmost Variants. International Journal of Foundations of Computer Science. 2016, roč. 27, č. 3, s. 359-373. ISSN 0129-0541. Dostupné z: http://www.worldscientific.com/doi/10.1142/S0129054116400141
Jazyk publikace:angličtina
Název publikace:Simple Matrix Grammars and Their Leftmost Variants
Název (cs):Jednoduché Maticové Gramatiky a jejich Nejlevější Varianty
Strany:359-373
Místo vydání:SG
Rok:2016
URL:http://www.worldscientific.com/doi/10.1142/S0129054116400141
Časopis:International Journal of Foundations of Computer Science, roč. 27, č. 3, SG
ISSN:0129-0541
DOI:10.1142/S0129054116400141
Klíčová slova
simple matrix grammars, leftmost derivations, generative power
Anotace
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.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs.iso-8859-2?id=10751}
}

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