Undecidability of the trace coding problem and some decidable cases

Warning

This publication doesn't include Institute of Computer Science. 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:	Equational logic of semigroups and applications Mathematical structures of algebra and geometry