Článek v časopise

MEDUNA Alexander a SOUKUP Ondřej. Jumping Scattered Context Grammars. Fundamenta Informaticae. Amsterdam: IOS Press, 2017, roč. 152, č. 1, s. 51-86. ISSN 0169-2968.
Jazyk publikace:angličtina
Název publikace:Jumping Scattered Context Grammars
Název (cs):Skákájící Gramatiky s Rozptýleným Kontextem
Strany:51-86
Místo vydání:NL
Rok:2017
Časopis:Fundamenta Informaticae, roč. 152, č. 1, Amsterdam, NL
ISSN:0169-2968
DOI:10.3233/FI-2017-1512
Klíčová slova

scattered context grammars, alternative derivation modes, generative power, computational completeness
Anotace
Koncept skákajících gramatik s rozptýleným kontextem vychází z jejich klasických neskákajících verzí, pracují ovšem odlišně. Derivaci ve skákající gramatice dle pravidla (A1, A2, ..., An) -> (x1, x2, ..., xn) také provedeme tak, že z větné formy současně vymažeme A1, A2, ..., An a vložíme x1, x2, ..., xn, ovšem potenciálně na jiné pozice, než na kterých se vymazané neterminály nacházely. Článek představuje a studuje gramatiky s rozptýleným kontextem pracující v devíti různých módech skákajících derivací. Každý z nich poskytuje výpočetní úplnost, článek proto dokazuje, že rodina rekurzivně spočetných jazyků je charakterizována skákajícími gramatikami s rozptýleným kontextem pracujícími v libovolném z představených derivačních módů. V závěru navíc uvádíme několik otevřených problémů.
BibTeX:
@ARTICLE{
   author = {Alexander Meduna and Ond{\v{r}}ej Soukup},
   title = {Jumping Scattered Context Grammars},
   pages = {51--86},
   journal = {Fundamenta Informaticae},
   volume = {152},
   number = {1},
   year = {2017},
   ISSN = {0169-2968},
   doi = {10.3233/FI-2017-1512},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs.iso-8859-2?id=10750}
}

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

DNSSEC [dnssec]