Detail publikace

Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes

MEDUNA Alexander a SOUKUP Ondřej. Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes. In: Proceedings of MEMICS'14. Brno: NOVPRESS s.r.o., 2014, s. 89-100. ISBN 978-80-214-5022-6.
Název česky
Výpočetní úplnost gramatik s rozptýleným kontextem vyplývající z jejich práce v různých derivačních módech
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Soukup Ondřej, Ing. (UIFS FIT VUT)
Abstrakt

Tento článek představuje a studuje celou škálu derivačních módů gramatik s rozptýleným kontextem. Tyto gramatiky jsou v základu stejné jako klasické gramatiky s rozptýleným kontextem, pouze mohou potenciálně při aplikaci pravidla po vymazání n neterminálu vložit nové podřetězce na jiné pozice, než se nacházeli vymazané neterminály.

Článek se zaměřuje na výzkum generativní síly gramatik s rozptýleným kontextem pracujících v těchto derivačních módech. Demonstruje, že jsou ve všech stále výpočetně úplné - tedy stále charakterizují rodinu rekursivně spočetných jazyků.
Rok
2014
Strany
89-100
Sborník
Proceedings of MEMICS'14
Konference
MEMICS'14 -- 9th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Telč, CZ
ISBN
978-80-214-5022-6
Vydavatel
NOVPRESS s.r.o.
Místo
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB10730,
   author = "Alexander Meduna and Ond\v{r}ej Soukup",
   title = "Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes",
   pages = "89--100",
   booktitle = "Proceedings of MEMICS'14",
   year = 2014,
   location = "Brno, CZ",
   publisher = "NOVPRESS s.r.o.",
   ISBN = "978-80-214-5022-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10730"
}
Nahoru