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, 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
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"
}
Nahoru