Nie jesteś zalogowany | Zaloguj się

Decidability of equivalence of deterministic one-way multitape finite automata

Prelegent(ci)
Lorenzo Clemente
Afiliacja
MIM UW
Termin
7 grudnia 2022 14:15
Pokój
p. 5050
Seminarium
Seminarium „Teoria automatów”

I will present an old decidability result by Harju and Karhumäki, as in the title. The original proof involves some very nice algebraic constructions, which constitute the motivation for this presentation. We start from the well-known problem of deciding equivalence of one-dimensional linear recursive sequences (LRS) over a field. We then recall that decidability holds even for coefficients in a division ring (noncommutative field). Using Harju and Karhumäki's ingenious trick, we reduce two-tape finite automata to one-dimensional LRS over a suitable division ring. The construction of the division ring is the crux of the approach: it relies on the existence of a total ordering of the free group, which is a nontrivial result.