Seminari del Dipartimento di Matematica

Seminario del 2023

Shortest accepted strings for two-way finite automata

nell'ambito della serie: COMPLEX ANALYSIS LAB

SEMINARIO INTERDISCIPLINARE

Finite automata are a model of computation in finite memory in theoretical computer science. An automaton gets a string of symbols as an input, and either accepts or rejects it. A deterministic two-way finite automaton (2DFA) has a finite set of states and works by moving over the string back and forth, changing its state. The question studied in this talk is how long could be the shortest string accepted by an $n$-state 2DFA, as a function of $n$. The previously known lower bound is of the order $\Omega(1.626^n)$, and the upper bound is $\binom{2n}{n+1}=O(\frac{1}{\sqrt{n}}4^n)$. In my talk, I construct a family of $n$-state automata with shortest accepted strings of length $\frac{3}{4} \cdot 2^n - 1$. Also I study a special case of direction-determinate automata (those that always remember in the current state whether the last move was to the left or to the right), and determine the maximum length of the shortest accepted string precisely as $\binom{n}{\lfloor\frac{n}{2}\rfloor}-1 = \Theta(\frac{1}{\sqrt{n}} 2^n)$.