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.
Další formáty:   BibTeX LaTeX RIS
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
Originální 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
Změnil Změnil: doc. Mgr. Michal Kunc, Ph.D., učo 2906. Změněno: 1. 9. 2007 11:26.
Anotace
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ěrNázev: Matematické struktury algebry a geometrie
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury algebry a geometrie
VytisknoutZobrazeno: 19. 9. 2024 19:43