Prof. RNDr. Alexander Meduna, CSc.

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. Les Ulis: EDP Sciences, 2009, roč. 43, č. 2, s. 365-378. ISSN 0988-3754.
Jazyk publikace:angličtina
Název publikace:On context-free rewriting with a simple restriction and its computational completeness
Název (cs):O bezkontextovém přepisování s jednoduchým omezením a jeho výpočetní úplnost
Strany:365-378
Místo vydání:FR
Rok:2009
Časopis:RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, roč. 43, č. 2, Les Ulis, FR
ISSN:0988-3754
URL:http://dx.doi.org/10.1051/ita/2009002 [HTML]
Klíčová slova
formal languages, context-free grammar, context-free rewriting system, derivation restriction, generative power.

Anotace
Č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ů.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=8834}
}

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