Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Determinization and Complementation of Streett Automata


Stefan Schwoon. Determinization and complementation of Streett automata. In Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors, Automata, Logics, and Infinite Games, volume 2500 of Lecture Notes in Computer Science, chapter 5, pages 79–91. Springer, 2002.


Streett automata are automata on infinite words. They differ from other formalisms in their acceptance condition which models strong fairness constraints. Again, their expressiveness is equal to that of Büchi automata; however, Streett automata can have an exponentially more succinct representation for certain properties. Here, we survey results about upper and lower bounds on the problems of determinization and complementation of Streett automata.

Suggested BibTeX entry:

    author = {Stefan Schwoon},
    booktitle = {Automata, Logics, and Infinite Games},
    chapter = {5},
    editor = {Erich Gr{\"a}del and Wolfgang Thomas and Thomas Wilke},
    pages = {79--91},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {Determinization and Complementation of {S}treett Automata},
    volume = {2500},
    year = {2002}

This work is not available online here.