Giovanna D’Agostino

Giovanna D'Agostino, Andrea Paradiso

Finite-state transducers and Wheeler automata are two well-established frameworks in formal language theory. While transducers extend finite-state automata by associating output words to input words, Wheeler automata are automata whose underlying graph admits a co-lexicographic sorting of states, giving rise to the class of Wheeler languages, a proper subclass of star-free regular languages with efficient indexing properties. In this work, we introduce the notion of sequential Wheeler transducers, a class of deterministic one-way transducers combining the Wheeler condition on the underlying automaton with a monotonicity requirement on the output function. We establish several fundamental properties of this class: closure under composition, and closure of Wheeler languages under inverse image of Wheeler transductions. We then develop a minimization theory by refining Choffrut's syntactic equivalence $\sim_f$ into a relation $\sim_f^c$, and prove a Myhill-Nerode-style theorem characterizing exactly the functions realizable by a sequential Wheeler transducer. Finally, we give a machine-independent characterization of Wheeler functions in terms of the behavior of the function. These results lay the groundwork for a broader structural theory of Wheeler transducers, and we outline open problems concerning decidability, complexity, non-deterministic extensions, and logical characterizations.

Giovanna D'Agostino, Nicola Cotumaccio, Alberto Policriti et al.

The states of a deterministic finite automaton A can be identified with collections of words in Pf(L(A)) -- the set of prefixes of words belonging to the regular language accepted by A. But words can be ordered and among the many possible orders a very natural one is the co-lexicographic one. Such naturalness stems from the fact that it suggests a transfer of the order from words to the automaton's states. In a number of papers automata admitting a total ordering of states coherent with the ordering of the set of words reaching them have been proposed. Such class of ordered automata -- the Wheeler automata -- turned out to be efficiently stored/searched using an index. Unfortunately not all automata can be totally ordered as previously outlined. However, automata can always be partially ordered and an intrinsic measure of their complexity can be defined and effectively determined, as the minimum width of one of their admissible partial orders. As shown in previous works, this new concept of width of an automaton has useful consequences in the fields of graph compression, indexing data structures, and automata theory. In this paper we prove that a canonical, minimum-width, partially-ordered automaton accepting a language L -- dubbed the Hasse automaton H of L -- can be exhibited. H provides, in a precise sense, the best possible way to (partially) order the states of any automaton accepting L, as long as we want to maintain an operational link with the (co-lexicographic) order of Pf(L(A)). Using H we prove that the width of the language can be effectively computed from the minimum automaton recognizing the language. Finally, we explore the relationship between two (often conflicting) objectives: minimizing the width and minimizing the number of states of an automaton.