| KUNC, Michal. The trace coding problem is undecidable (extended abstract). In Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings. Berlin: Springer-Verlag, 2001, s. 603-614. ISBN 3-540-42287-0. |
Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{366131,
author = {Kunc, Michal},
address = {Berlin},
booktitle = {Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings},
language = {eng},
location = {Berlin},
isbn = {3-540-42287-0},
pages = {603-614},
publisher = {Springer-Verlag},
title = {The trace coding problem is undecidable (extended abstract)},
year = {2001}
}
TY - JOUR
ID - 366131
AU - Kunc, Michal
PY - 2001
TI - The trace coding problem is undecidable (extended abstract)
PB - Springer-Verlag
CY - Berlin
SN - 3540422870
N2 - 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 Ochmanski in 1988. We also show its decidability when restricted to instances with domain monoids defined by acyclic dependence graphs.
ER -
KUNC, Michal. The trace coding problem is undecidable (extended abstract). In \textit{Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings}. Berlin: Springer-Verlag, 2001, s.~603-614. ISBN~3-540-42287-0.
|
