Abstract
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 Ochmański in 1988. We also show its decidability when restricted to instances with domain monoids defined by acyclic dependence graphs.
This research was partially supported by the Ministry of Education of the Czech Republic under the project MSM 143100009.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bruyère, V., De Felice, C.: Coding and strong coding in trace monoids. In Proc. STACS’95, LNCS 900, Springer (1995) 373–384.
Bruyère, V., De Felice, C.: On the existence of codings between trace monoids. Journal of Automata, Languages and Combinatorics 4 (1999) 87–100.
Bruyère, V., De Felice, C., Guaiana, G.: On some decision problems for trace codings. Theoretical Computer Science 148 (1995) 227–260.
Diekert, V., Métivier, Y.: Partial commutation and traces. In Handbook of Formal Languages, Vol. 3, Springer (1997) 457–533.
Diekert, V., Muscholl, A.: Code problems on traces. In Proc. MFCS’96, LNCS 1113, Springer (1996) 2–17.
Diekert, V., Muscholl, A., Reinhardt, K.: On codings of traces. In Proc. STACS’95, LNCS 900, Springer (1995) 385–396.
Duboc, C.: On some equations in free partially commutative monoids. Theoretical Computer Science 46 (1986) 159–174
Kunc, M.: Undecidability of the trace coding problem and some decidable cases. manuscript (2001). http://www.math.muni.cz/~kunc
Mazurkiewicz, A.: Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus (1977).
Ochmański, E.: On morphisms of trace monoids. In Proc. STACS’88, LNCS 294, Springer (1988) 346–355.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kunc, M. (2001). The Trace Coding Problem Is Undecidable. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 2001. Lecture Notes in Computer Science, vol 2076. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48224-5_50
Download citation
DOI: https://doi.org/10.1007/3-540-48224-5_50
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42287-7
Online ISBN: 978-3-540-48224-6
eBook Packages: Springer Book Archive