Undecidability of the trace coding problem and some decidable cases

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Název česky Nerozhodnutelnost problému stopových kódování a některé rozhodnutelné případy
Autoři

KUNC Michal

Rok publikování 2004
Druh Článek v odborném periodiku
Časopis / Zdroj Theoretical Computer Science
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www http://authors.elsevier.com/sd/article/S0304397503004468
Obor Obecná matematika
Klíčová slova Partial commutativity; Trace monoid; Coding; Concurrency
Popis V práci je zaveden a zkoumán pojem slabých morfismů monoidů stop s cílem vyřešit problém rozhodování existence kódování mezi monoidy stop. Je dokázáno, že tento problém není rekurzívně vyčíslitelný, čímž je zodpovězena otázka položená Ochmanskim v roce 1988. Na druhou stranu je dokázána rozhodnutelnost zúžení tohoto problému na instance, jejichž doménové monoidy jsou definovány acyklickými grafy závislosti. Rovněž je částečně zodpovězena otázka Diekerta z roku 1990 o počtu volných monoidů potřebných k zakódování daného monoidu stop do jejich přímého součinu.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.