2004
Undecidability of the trace coding problem and some decidable cases
KUNC, MichalZákladní údaje
Originální název
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
KUNC, Michal (203 Česká republika, garant)
Vydání
Theoretical Computer Science, Amsterdam, Elsevier, 2004, 0304-3975
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 0.676
Kód RIV
RIV/00216224:14310/04:00009880
Organizační jednotka
Přírodovědecká fakulta
UT WoS
000187222600019
Klíčová slova anglicky
Partial commutativity; Trace monoid; Coding; Concurrency
Štítky
Změněno: 23. 1. 2006 15:33, doc. Mgr. Michal Kunc, Ph.D.
V originále
We introduce and investigate the notion of weak morphisms of trace monoids with the aim of dealing with the problem of deciding the existence of codings between trace monoids. We prove that this problem is not recursively enumerable, which answers the question raised by Ochmanski in 1988. On the other hand, we show its decidability when restricted to instances with domain monoids defined by acyclic dependence graphs. We also partially answer the question of Diekert from 1990 about the number of free monoids needed for encoding a given trace monoid into their direct product.
Česky
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.
Návaznosti
| GA201/01/0323, projekt VaV |
| ||
| MSM 143100009, záměr |
|