Detail publikace
On context-free rewriting with a simple restriction and its computational completeness
MASOPUST Tomáš a MEDUNA Alexander. On context-free rewriting with a simple restriction and its computational completeness. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, roč. 43, č. 2, 2009, s. 365-378. ISSN 0988-3754.
Název česky
O bezkontextovém přepisování s jednoduchým omezením a jeho výpočetní úplnost
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Abstrakt
Článek diskutuje bezkontextové přepisovací systémy, v nichž existují dvě konečné disjunktní množiny pravidel, a symbol, označovaný jako podmínka aplikovatelnosti, je přiřazen ke každému pravidlu v obou množinách. V jedné množině jsou pravidla, která jsou aplikovatelná pouze tehdy, pokud se k ním přiřazené symboly vyskytuje ve větné formě, zatímco ve druhé množině jsou pravidla, která jsou aplikovatelná pouze tehdy, pokud se k ním přiřazené symboly nevyskytují ve větné formě. Článek demonstruje, že takovéto přepisující systémy jsou výpočetně úplné. V závěru je pak odvozeno několik důsledků.
Rok
2009
Strany
365-378
Časopis
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, roč. 43, č. 2, ISSN 0988-3754
Vydavatel
EDP Sciences
UT WoS
000264879300012
BibTeX
@ARTICLE{FITPUB8834, author = "Tom\'{a}\v{s} Masopust and Alexander Meduna", title = "On context-free rewriting with a simple restriction and its computational completeness", pages = "365--378", journal = "RAIRO - Theoretical Informatics and Applications - Informatique Th\'{e}orique et Applications", volume = 43, number = 2, year = 2009, ISSN = "0988-3754", language = "english", url = "https://www.fit.vut.cz/research/publication/8834" }