Combinatorial structures connecting Latin squares and bireversible automata
2026-07-28 • Formal Languages and Automata Theory
Formal Languages and Automata Theory
AI summaryⓘ
The authors study certain types of automata called letter transducers, Mealy automata, and bireversible automata using ideas similar to Latin squares, which are special number grids. They compare the transitions in these automata to combinatorial objects like orthogonal arrays and nets, helping to understand their structure better. The paper shows how different automata classes can be described using these combinatorial tools and explains how operations like inversion relate to known mathematical transformations. Finally, the authors develop a concept called isotopisms that extend symmetry ideas from Latin squares to these automata, preserving important properties.
letter transducersMealy automatabireversible automataLatin squaresorthogonal arraysparastrophismsisotopismsreversible automatacombinatorial structures
Authors
Brian Curtin, Dmytro Savchuk
Abstract
This paper explores the theory of letter transducers, Mealy automata, and bireversible automata from a combinatorial perspective analogous to the theory of Latin squares. We view the sets of transitions of letter transducers as analogs of orthogonal arrays, and discuss two other combinatorial encodings of Mealy automata analogous to orthogonal pairs of Latin squares and to $(k,n)$-nets. We characterize various classes of automata (Mealy, reversible, invertible, bireversible) in terms of these combinatorial structures. In particular, we represent the inversion and dualization of transducers as parastrophisms. Further, similarly to the notion of the isotopisms of the quasigroups associated to Latin squares, we develop the notion of isotopisms of letter transducers generalizing transducer symmetry and preserving the class of bireversible automata.