Informace o publikaci
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 | |
| 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 | |
| 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: |