State Complexity of Reversals of Deterministic Finite Automata with Output

Abstract

We investigate the worst-case state complexity of reversals of deterministic finite automata with output (DFAOs). In these automata, each state is assigned some output value, rather than simply being labelled final or non-final. This directly generalizes the well-studied problem of determining the worst-case state complexity of reversals of ordinary deterministic finite automata. If a DFAO has $n$ states and $k$ possible output values, there is a known upper bound of $k^n$ for the state complexity of reversal. We show this bound can be reached with a ternary input alphabet. We conjecture it cannot be reached with a binary input alphabet except when $k=2$, and give a lower bound for the case $3\le k<n$. We prove that the state complexity of reversal depends solely on the transition monoid of the DFAO and the mapping that assigns output values to states.

18 pages, 3 tables. Added missing affiliation/funding information