Další formáty:
BibTeX
LaTeX
RIS
@article{490364,
author = {Kunc, Michal},
article_location = {Amsterdam},
article_number = {1-3},
keywords = {Partial commutativity; Trace monoid; Coding; Concurrency},
language = {eng},
issn = {0304-3975},
journal = {Theoretical Computer Science},
title = {Undecidability of the trace coding problem and some decidable cases},
url = {http://authors.elsevier.com/sd/article/S0304397503004468},
volume = {310},
year = {2004}
}
TY - JOUR
ID - 490364
AU - Kunc, Michal
PY - 2004
TI - Undecidability of the trace coding problem and some decidable cases
JF - Theoretical Computer Science
VL - 310
IS - 1-3
SP - 393
EP - 393
PB - Elsevier
SN - 03043975
KW - Partial commutativity
KW - Trace monoid
KW - Coding
KW - Concurrency
UR - http://authors.elsevier.com/sd/article/S0304397503004468
N2 - 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.
ER -
KUNC, Michal. Undecidability of the trace coding problem and some decidable cases. \textit{Theoretical Computer Science}. Amsterdam: Elsevier, 2004, roč.~310, 1-3, s.~393-456. ISSN~0304-3975.
|
