On regular languages with an associated total order
The presentation explores the idea of introducing the notion of a total order to regular languages and deterministic finite automata (DFAs) with a focus on the definitions as given in a paper by Shyr and Thierrin in 1974. We discuss some properties and consequences of these definitions and present a selection of known results mainly related to state complexity. Finally, we outline a series of interesting open problems that are going to be subject to further investigation.