On Deterministic Finite Automata Equipped with Partial Orders
Jürgen Dassow · International Journal of Foundations of Computer Science · 2025
We consider deterministic finite automata equipped with a reflexive partial order on the set of states which is preserved by the transition function. We define the width of a deterministic finite automaton by the minimal width of such reflexive partial orders. For a regular language, we define its width as the minimal width of deterministic finite automata accepting the language. We discuss the unary case, study the relation between state complexity and width, and investigate the behaviour of the width under operations.