Informace o publikaci
Undecidability of the trace coding problem and some decidable cases
| Název česky | Nerozhodnutelnost problému stopových kódování a některé rozhodnutelné případy |
|---|---|
| Autoři | |
| Rok publikování | 2004 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theoretical Computer Science |
| Fakulta / Pracoviště MU | |
| 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: |