Undecidability of the trace coding problem and some decidable cases

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F04%3A00009880" target="_blank" >RIV/00216224:14310/04:00009880 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Undecidability of the trace coding problem and some decidable cases
Original language 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.
Czech name
Nerozhodnutelnost problemu stopovych kodovani a nektere rozhodnutelne pripady
Czech description
V praci je zaveden a zkouman pojem slabych morfismu monoidu stop s cilem vyresit problem rozhodovani existence kodovani mezi monoidy stop. Je dokazano, ze tento problem neni rekurzivne vycislitelny, cimz je zodpovezena otazka polozena Ochmanskim v roce 1988. Na druhou stranu je dokazana rozhodnutelnost zuzeni tohoto problemu na instance, jejichz domenove monoidy jsou definovany acyklickymi grafy zavislosti. Rovnez je castecne zodpovezena otazka Diekerta z roku 1990 o poctu volnych monoidu potrebnych k zakodovani daneho monoidu stop do jejich primeho soucinu.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/GA201%2F01%2F0323" target="_blank" >GA201/01/0323: Equational logic of semigroups and applications</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)