Finite-State Transducers in the Wheeler Setting

We investigate the interaction between Wheeler automata and finite-state subsequential transducers. Wheeler languages form a structurally well-behaved subclass of the regular languages and provide an automata-theoretic foundation for efficient indexing and compression techniques inspired by the Burrows-Wheeler transform. We introduce a class of Wheeler transducers whose underlying input automata are Wheeler and whose output functions satisfy a piecewise monotonicity condition on the sets of words reaching each state. We show that this class is closed under composition and that inverse images of Wheeler languages under Wheeler transductions are again Wheeler languages. We then study minimization by refining Choffrut’s syntactic congruence for subsequential functions with convexity and piecewise monotonicity constraints. This yields a Myhill-Nerode-style characterization of the functions realizable by Wheeler transducers. Finally, we provide a machine-independent characterization of Wheeler functions in terms of the behavior of monotone sequences and piecewise monotonicity. These results constitute a first step toward a structural theory of transductions compatible with the Wheeler setting.