Detail publikace

Jumping Scattered Context Grammars

MEDUNA Alexander a SOUKUP Ondřej. Jumping Scattered Context Grammars. Fundamenta Informaticae, roč. 152, č. 1, 2017, s. 51-86. ISSN 0169-2968.
Název česky
Skákájící Gramatiky s Rozptýleným Kontextem
Typ
článek v časopise
Jazyk
angličtina
Autoři
Abstrakt

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ů.

Rok
2017
Strany
51-86
Časopis
Fundamenta Informaticae, roč. 152, č. 1, ISSN 0169-2968
Vydavatel
IOS Press
DOI
UT WoS
000398597900004
EID Scopus
BibTeX
@ARTICLE{FITPUB10750,
   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 = "https://www.fit.vut.cz/research/publication/10750"
}
Nahoru