2007
The simplest language where equivalence of finite substitutions is undecidable
KUNC, MichalZákladní údaje
Originální název
The simplest language where equivalence of finite substitutions is undecidable
Název česky
Nejjednodušší jazyk, na němž je ekvivalence konečných substitucí nerozhodnutelná
Autoři
Vydání
Berlin, Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings, s. 365-375, 2007
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Kód RIV
RIV/00216224:14310/07:00020433
Organizační jednotka
Přírodovědecká fakulta
ISBN
978-3-540-74239-5
UT WoS
000250044600032
Klíčová slova anglicky
Finite substitution; Language equation; Finite transducer; Regular language; Equivalence problem
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 12. 12. 2007 16:58, doc. Mgr. Michal Kunc, Ph.D.
V originále
We show that it is undecidable whether two finite substitutions agree on the binary language a*b. This in particular means that equivalence of nondeterministic finite transducers is undecidable even for two-state transducers with unary input alphabet and whose all transitions start from the initial state.
Česky
Ukazujeme, že není možné rozhodovat, zda se dvě konečné substituce shodují na binárním jazyce a*b. To mimo jiné znamená, že ekvivalence nedeterministických konečných převodníků je nerozhodnutelná dokonce pro dvoustavové převodníky s unární vstupní abecedou, jejichž všechny přechody vedou z počátečního stavu.
Návaznosti
| GA201/06/0936, projekt VaV |
| ||
| MSM0021622409, záměr |
|