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

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.