The trace coding problem is undecidable (extended abstract)
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F01%3A00004315" target="_blank" >RIV/00216224:14310/01:00004315 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
The trace coding problem is undecidable (extended abstract)
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2001
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings
ISBN
3-540-42287-0
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
603
Publisher name
Springer-Verlag
Place of publication
Berlin
Event location
Berlin
Event date
Jan 1, 2001
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—