4
$\begingroup$

There are a lot of work about bounds on the complementation of Streett automata (see e.g. this paper). They talk about the general setting of nondeterministic Streett automata. But what about deterministic ones?

Streett automata are closed under determinisation although with an exponential blow-up. And complementation has an exponential complexity. So I would suppose that complementation of deterministic Streett automata would be simpler, maybe polynomial?

So, how do I complement deterministic Streett automata? Is the task computationally easy?

Edit: as far as I can tell, this question is equivalent to asking how to translate a deterministic Rabin automaton to an equivalent deterministic Streett automaton.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

This paper gives an example of a deterministic Rabin automaton with $\mathcal{O}(n)$ states such that there is no nondeterministic (hence no deterministic) equivalent Streett automaton with less than $2^n$ states.

I guess there is no hope for a polynomial complementation, even if the Streett automaton is deterministic.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's exactly what I was looking for, thanks! $\endgroup$
    – Nicola Gigante
    Commented Nov 1, 2022 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.