The trace coding problem is undecidable (extended abstract)

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KUNC Michal

Year of publication 2001
Type Article in Proceedings
Conference Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings
MU Faculty or unit

Faculty of Science

Citation
Field General mathematics
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.