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