The trace coding problem is undecidable (extended abstract)
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
The trace coding problem is undecidable (extended abstract)
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
The trace coding problem is undecidable (extended abstract)
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2001
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Automata, Languages and Programming : 28th International Colloquium, ICALP 2001, Proceedings
ISBN
3-540-42287-0
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
603
Název nakladatele
Springer-Verlag
Místo vydání
Berlin
Místo konání akce
Berlin
Datum konání akce
1. 1. 2001
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—