The simplest language where equivalence of finite substitutions is undecidable

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Název česky Nejjednodušší jazyk, na němž je ekvivalence konečných substitucí nerozhodnutelná
Autoři

KUNC Michal

Rok publikování 2007
Druh Článek ve sborníku
Konference Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www http://dx.doi.org/10.1007/978-3-540-74240-1_32
Obor Obecná matematika
Klíčová slova Finite substitution; Language equation; Finite transducer; Regular language; Equivalence problem
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.