Undecidability of the trace coding problem and some decidable cases

KUNC, Michal. Undecidability of the trace coding problem and some decidable cases. Theoretical Computer Science. Amsterdam: Elsevier, 2004, vol. 310, 1-3, p. 393-456. ISSN 0304-3975.

Basic information

• Original name: Undecidability of the trace coding problem and some decidable cases
• Name in Czech: Nerozhodnutelnost problému stopových kódování a některé rozhodnutelné případy
• Authors: KUNC, Michal (203 Czech Republic, guarantor).
• Edition: Theoretical Computer Science, Amsterdam, Elsevier, 2004, 0304-3975.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10101 Pure mathematics
• Country of publisher: Netherlands
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• Impact factor: Impact factor: 0.676
• RIV identification code: RIV/00216224:14310/04:00009880
• Organization unit: Faculty of Science
• UT WoS: 000187222600019
• Keywords in English: Partial commutativity; Trace monoid; Coding; Concurrency
• Tags: coding, concurrency, Partial commutativity, Trace monoid

Abstract

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.

Abstract (in Czech)

V práci je zaveden a zkoumán pojem slabých morfismů monoidů stop s cílem vyřešit problém rozhodování existence kódování mezi monoidy stop. Je dokázáno, že tento problém není rekurzívně vyčíslitelný, čímž je zodpovězena otázka položená Ochmanskim v roce 1988. Na druhou stranu je dokázána rozhodnutelnost zúžení tohoto problému na instance, jejichž doménové monoidy jsou definovány acyklickými grafy závislosti. Rovněž je částečně zodpovězena otázka Diekerta z roku 1990 o počtu volných monoidů potřebných k zakódování daného monoidu stop do jejich přímého součinu.

Links

• GA201/01/0323, research and development project: Name: Ekvacionální logika pologrup a aplikace

Investor: Czech Science Foundation, Equational logic of semigroups and applications

• MSM 143100009, plan (intention): Name: Matematické struktury algebry a geometrie

Investor: Ministry of Education, Youth and Sports of the CR, Mathematical structures of algebra and geometry