You are not logged in | Log in

Decidability of equivalence of deterministic one-way multitape finite automata

Speaker(s)
Lorenzo Clemente
Affiliation
MIM UW
Date
Dec. 7, 2022, 2:15 p.m.
Room
room 5050
Seminar
Seminar Automata Theory

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.