The trace coding problem is undecidable (extended abstract)

KUNC, Michal. The trace coding problem is undecidable (extended abstract). In Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings. Berlin: Springer-Verlag, 2001, s. 603-614. ISBN 3-540-42287-0.

Základní údaje

Originální název

The trace coding problem is undecidable (extended abstract)

Autoři

KUNC, Michal (203 Česká republika, garant)

Vydání

Berlin, Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings, s. 603-614, 2001

Nakladatel

Springer-Verlag

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Kód RIV

RIV/00216224:14310/01:00004315

Organizační jednotka

Přírodovědecká fakulta

ISBN

3-540-42287-0

---

Anotace

V originále

We introduce the notion of weak morphisms of trace monoids and use it to deal 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. We also show its decidability when restricted to instances with domain monoids defined by acyclic dependence graphs.

---

Návaznosti

MSM 143100009, záměr

Název: Matematické struktury algebry a geometrie Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury algebry a geometrie