On Prefix-Sorting Finite Automata.
Jarno Alanko, Alberto Policriti, Nicola Prezza · arXiv (Cornell University) · 2019
Being able to efficiently test the membership of a word in a formal language is, arguably, one of the most fundamental problems in computer science. In this paper, we combine techniques from string processing (specifically, prefix-sorting) and automata theory (specifically, DFA minimization) to speed up solutions for this problem on languages described by finite automata. Prefix sorting can be generalized to objects more complex than strings: the recent notion of Wheeler graph extends this concept to labeled graphs such as finite-state automata. A Wheeler graph admits a co-lexicographic ordering of its nodes and opens up the possibility of building fast and small data structures supporting powerful path queries on the graph (i.e. substring closure of the accepting language when the graph represents a NFA). However, while several structures including strings, trees, and de Bruijn graphs can always be prefix-sorted in linear time, the situation on general graphs is more complicated: not all graphs admit such an ordering, and a recent result shows that the problem of identifying them is NP-complete even for acyclic NFAs. In this paper, we provide several results showing that the problem becomes tractable on DFAs. Our results include polynomial-time algorithms to (i) recognize and prefix-sort Wheeler finite automata (even admitting some limited amount of nondeterminism), (ii) minimize Wheeler DFAs, and (iii) compute the minimum Wheeler DFA recognizing the same language of any acyclic DFA. Our last contribution is a big step towards a complete solution to the (hard) problem of indexing graphs for efficient path queries: our minimization theorem essentially solves the deterministic-acyclic case with a solution of provably minimum size.