The Containment Problem for Unambiguous Register Automata
- Speaker(s)
- Karin Quaas
- Affiliation
- Universität Leipzig
- Date
- May 22, 2019, 2:15 p.m.
- Room
- room 5050
- Seminar
- Seminar Automata Theory
We investigate the complexity of the containment problem:
given a register automaton A and an unambiguous register automaton B,
given a register automaton A and an unambiguous register automaton B,
is the language accepted by A contained in the language accepted by B?
We prove that the problem is decidable and give upper bounds on the computational complexity.
We also study the case where the register automata are defined over ordered domains,
and where the registers can take values that did not occur in the input word (so called register automata with guessing).
We prove that the problem is decidable and give upper bounds on the computational complexity.
We also study the case where the register automata are defined over ordered domains,
and where the registers can take values that did not occur in the input word (so called register automata with guessing).
This is joint work with Antoine Mottet (Charles University, Prague).