SEMINAR: Groups and Combinatorics Seminar: Some results on constant maps in the transition monoid of an automaton

Groups and Combinatorics Seminar

Tim Boykett (Johannes Kepler Universitat Linz, Austria)

will speak on

Some results on constant maps in the transition monoid of an automaton

at 12 noon in Maths Lecture Room 2 on Tuesday 16 February.

Abstract: We investigate finite state automata and are interested in the situation when certain words can map any given state to a fixed terminal state. These so called reset words correspond to constant maps or right zeroes in the transition monoid of the automaton. A conjecture of J. Cerny states that if an automaton has a reset word, then it has one of length less than or equal to (n-1)^2, where n is the number of states. This bound is reached by a class defined by Cerny and 8 known sporadic examples.

In this talk I will present an outline of some results including some classes with much smaller minimal reset words. I will also outline several open areas of work.

All welcome.