Undecidability of the trace coding problem and some decidable cases

Investor logo

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 2004
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Science

Citation
Web http://authors.elsevier.com/sd/article/S0304397503004468
Field General mathematics
Keywords Partial commutativity; Trace monoid; Coding; Concurrency
Description 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.
Related projects:

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