The simplest language where equivalence of finite substitutions is undecidable

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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:	Matematické struktury a jejich fyzikální aplikace Algebraické metody v teorii automatů a formálních jazyků