Contact

Director

Prof. Dr. Ernst-Rüdiger Olderog

Department of Computing Science
FK II
University of Oldenburg
D-26111 Oldenburg, Germany

Coordinator

Ira Wempe

Department of Computing Science
FK II
University of Oldenburg
D-26111 Oldenburg, Germany

[Invited Talk 11.09.2018] Quaas

On the Containment Problem for Unambiguous Register Automata

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.

(Changed: 20 Jun 2024)  | 
Zum Seitananfang scrollen Scroll to the top of the page