Detail publikace

Simple Matrix Grammars and Their Leftmost Variants

MEDUNA, A.; SOUKUP, O. Simple Matrix Grammars and Their Leftmost Variants. International Journal of Foundations of Computer Science, 2016, vol. 27, no. 3, p. 359-373. ISSN: 0129-0541.
Název česky
Jednoduché Maticové Gramatiky a jejich Nejlevější Varianty
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Soukup Ondřej, Ing., Ph.D.
URL
Klíčová slova

simple matrix grammars, leftmost derivations, generative power

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
10.1142/S0129054116400141
UT WoS
000378637600005
EID Scopus
2-s2.0-84973547707
BibTeX 
@article{BUT130903,
  author="Alexandr {Meduna} and Ondřej {Soukup}",
  title="Simple Matrix Grammars and Their Leftmost Variants",
  journal="International Journal of Foundations of Computer Science",
  year="2016",
  volume="27",
  number="3",
  pages="359--373",
  doi="10.1142/S0129054116400141",
  issn="0129-0541",
  url="http://www.worldscientific.com/doi/10.1142/S0129054116400141"
}
Nahoru