Hardness and Approximation for Compressing Deterministic Finite Automata

Philip Bille, Inge Li Gørtz, Christoffer Krogh +1

The delayed deterministic finite automaton (${\text{D}}^2\text{FA}$) is a powerful tool for compressing the prohibitively large deterministic finite automata (DFAs) used in modern si…