The trace coding problem is undecidable (extended abstract)

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Autoři

KUNC Michal

Rok publikování 2001
Druh Článek ve sborníku
Konference Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Obor Obecná matematika
Popis 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.
Související projekty:

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