Undecidability of the trace coding problem and some decidable cases

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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:	Ekvacionální logika pologrup a aplikace Matematické struktury algebry a geometrie