Boundedness problems for finite automata

Christof Löding
RWTH Aachen
Friday, 27 November, 2009 (All day)
NO Building

We consider finite automata (on words or trees) that besides
accepting or rejecting their input also compute a value for each
accepted input. This value is determined by the use of counters in the
automaton that can be incremented or reset to zero. The values of the
counters do not influence the controlflow of the automaton, they are
only used to determine the value of the run on the input.

Such automata on finite words have been used by Kirsten (under the
name of nested distance desert automata) to solve the (restricted)
star-height problem: Given a regular language, what is the minimal
number of nested stars in a regular expression defining the language?
In this application, the value of a run is the maximal value reached
by one of the counters during the run. The value of an input is the
minimal value of one of the runs on the input.  The problem of
star-height is reduced to the limitedness problem for these automata:
Is the mapping computed by the automaton on its accepted inputs
bounded? This problem is shown to be decidable using algebraic
techniques.

In recent work a general theory of such automata has been
developed. The purpose of the talk is to give an introduction and an
overview of this subject.