A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression
Nicola Cotumaccio Β· arXiv (Cornell University) Β· 2023
The model of generalized automata, introduced by Eilenberg in 1974, allows representing a regular language more concisely than conventional automata by allowing edges to be labeled not only with characters, but also strings. Giammaresi and Montalbano introduced a notion of determinism for generalized automata [STACS 1995]. While generalized deterministic automata retain many properties of conventional deterministic automata, the uniqueness of a minimal generalized deterministic automaton is lost. In the first part of the paper, we show that the lack of uniqueness can be explained by introducing a set π²(π) associated with a generalized automaton π. The set π²(π) is always trivially equal to the set of all prefixes of the language recognized by the automaton, if π is a conventional automaton, but this need not be true for generalized automata. By fixing π²(π), we are able to derive for the first time a full Myhill-Nerode theorem for generalized automata, which contains the textbook Myhill-Nerode theorem for conventional automata as a degenerate case. In the second part of the paper, we show that the set π²(π) leads to applications for pattern matching and data compression. Wheeler automata [TCS 2017, SODA 2020] are a popular class of automata that can be compactly stored using e log Ο (1 + o(1)) + O(e) bits (e being the number of edges, Ο being the size of the alphabet) in such a way that pattern matching queries can be solved in OΜ(m) time (m being the length of the pattern). In the paper, we show how to extend these results to generalized automata. More precisely, a Wheeler generalized automata can be stored using π’ log Ο (1 + o(1)) + O(e + rn) bits so that pattern matching queries can be solved in OΜ(rm) time, where π’ is the total length of all edge labels, r is the maximum length of an edge label and n is the number of states.