The trace coding problem is undecidable (extended abstract)

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, p. 603-614. ISBN 3-540-42287-0.

Basic information

Original name

The trace coding problem is undecidable (extended abstract)

Authors

KUNC, Michal (203 Czech Republic, guarantor)

Edition

Berlin, Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings, p. 603-614, 2001

Publisher

Springer-Verlag

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10101 Pure mathematics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

RIV identification code

RIV/00216224:14310/01:00004315

Organization unit

Faculty of Science

ISBN

3-540-42287-0

---

Abstract

V originále

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.

---

Links

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