Deciding Definability by Deterministic Regular Expressions

Prelegent(ci)

Claire David

Afiliacja

Université Paris-Est Marne-la-Vallée

Termin

5 czerwca 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with W.Czerwinski, K. Losemann, W. Martens

Seminarium

Seminarium „Teoria automatów”

---

Intuitively, a regular expression is deterministic if, when reading a
word from left to right without looking ahead, one always knows where in
the expression the next symbol will be matched. The set of languages
definable by such regular expressions is a strict subset of the set of
all regular languages.
We investigate the complexity of deciding whether a given regular
language can be defined with a deterministic regular expression. Our
main technical result shows that the problem is \pspace-complete if the
input language is represented as a regular expression or
nondeterministic finite automaton.

---