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.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10101 Pure mathematics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
RIV identification code RIV/00216224:14310/01:00004315
Organization unit Faculty of Science
ISBN 3-540-42287-0
Changed by Changed by: doc. Mgr. Michal Kunc, Ph.D., učo 2906. Changed: 1/9/2007 11:26.
Abstract
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
PrintDisplayed: 3/5/2024 10:16