Undecidability of the trace coding problem and some decidable cases

DOI10.1016/J.TCS.2003.08.004zbMath1071.68043OpenAlexW2034389264MaRDI QIDQ1884985

Michal Kunc

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.08.004

zbMATH Keywords

CodingConcurrencyTrace monoidPartial commutativity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (2)

The inclusion structure of partially lossy queue monoids and their trace submonoids ⋮ The Trace Monoids in the Queue Monoid and in the Direct Product of Two Free Monoids

Cites Work

• On some decision problems for trace codings
• Any lifting of a trace coding is a word coding
• On some equations in free partially commutative monoids
• Combinatorial problems of commutation and rearrangements
• Coding and strong coding in trace monoids
• On codings of traces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Undecidability of the trace coding problem and some decidable cases