Dr. Karin Quaas, Universität Leipzig

Abstract:

We study the containment problem for unambiguous register automata. Register automata, introduced by Kaminski and Francez in 1994, extend finite automata with a finite set of registers. Register automata can process data words, i.e., finite words over an infinite data domain; the registers are used to store data coming from the input word for later comparisons. A register automaton is unambiguous if it has at most one accepting run for every input data word. The class of languages recognized by these automata is not closed under complement, thereby preventing a classical reduction of the containment problem to the
emptiness problem for register automata. We will present a proof that the containment problem for unambiguous register automata is decidable, based on a reduction to a reachability problem on some finite graph.

This is joint work with Antoine Mottet.