# Boundedness problems for finite automata

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.