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.
Date and Venue
Start Date
Venue
Room FC1 119 (Math Bldg., FCUP)
Speaker
Viktor Olejár
Speaker's Institution
Mathematical Institute of the Slovak Academy of Sciences, Pavol Jozef Šafárik University in Košice
Files
semVO.pdf97.28 KB
Area
Semigroups, Automata and Languages