R-automata

R-automata are finite state machines with a finite number of unbounded counters which can be left unchanged, incremented, or reset to zero along the transitions. We define the language accepted by such a machine relative to a natural number D as a set of words for which there is a run along which no counter exceeds D. We study the existential universality problem, i.e., the problem whether there is D such that the corresponding language is universal. The decidability proof for the universality reformulates the claim in the language of finite monoids and uses factorization forest theorem.

The presentation focuses on the introduction and motivation of the model and the problem. The proof will be sketched together with the main concepts. There is no specific knowledge required to follow the seminar (expect for finite automata).