@incollection(Buchi/66/Decision, author = "Richard B{\"{u}}chi", year = "1966", title = "Symposium on Decision Problems: On a Decision Method in Restricted Second Order Arithmetic", booktitle = "Logic, Methodology and Philosophy of Science, Proceeding of the 1960 International Congress", series = "Studies in Logic and the Foundations of Mathematics", volume = "44", publisher = "Elsevier", pages = "1--11", doi = "10.1016/S0049-237X(09)70564-6", ) @inproceedings(Cai+Zhang/11/Tight+Lower, author = "Yang Cai and Ting Zhang", year = "2011", title = "A Tight Lower Bound for Streett Complementation", booktitle = "Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)", pages = "339--350", doi = "10.4230/LIPIcs.FSTTCS.2011.339", ) @inproceedings(Cai+Zhang/11/Tight+Upper, author = "Yang Cai and Ting Zhang", year = "2011", title = "Tight Upper Bounds for Streett and Parity Complementation", booktitle = "Proceedings of the 20th Conference on Computer Science Logic (CSL 2011)", publisher = "Dagstuhl Publishing", pages = "112--128", doi = "10.4230/LIPIcs.CSL.2011.112", ) @inproceedings(Cai+Zhang+Luo/09/Improved, author = "Yang Cai and Ting Zhang and Haifeng Luo", year = "2009", title = "An Improved Lower Bound for the Complementation of Rabin Automata", booktitle = "Proceedings of the 24th Annual IEEE Symposium on Logic In Computer Science", publisher = "IEEE Computer Society", pages = "167--176", doi = "10.1109/LICS.2009.13", ) @article(Choueka/74/Theories, author = "Yaacov Choueka", year = "1974", title = "Theories of automata on $\omega $-types: a simplified appraoch", journal = "Journal of Computer and System Science", volume = "8", number = "2", pages = "117--141", doi = "10.1016/S0022-0000(74)80051-6", ) @inproceedings(Colcombet+Zdanowski/09/Tight, author = "Thomas Colcombet and Konrad Zdanowski", year = "2009", title = "A Tight Lower Bound for Determinization of Transition Labeled {B\"{u}chi} Automata", booktitle = "Proceedings of the 36th Internatilonal Collogquium on Automata, Languages and Programming (ICALP 2009)", publisher = "Springer-Verlag", pages = "151--162", doi = "10.1007/978-3-642-02930-1\_13", ) @book(Francez/1986/Fairness, author = "Nissim Francez", year = "1986", title = "Fairness", publisher = "Springer-Verlag New York, Inc.", ) @inproceedings(Francez/84/Generalized, author = "Nissim Francez and Dexter Kozen", year = "1984", title = "Generalized fair termination", booktitle = "Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL'84)", publisher = "ACM", pages = "46--53", doi = "10.1145/800017.800515", ) @inproceedings(Gurevich+Harrington/82/Trees, author = "Yuri Gurevich and Leo Harrington", year = "1982", title = "Trees, Automata, and Games", booktitle = "Proceedings of the 14th annual ACM symposium on Theory of computing (STOC'82)", pages = "60--65", doi = "10.1145/800070.802177", ) @incollection(Kupferman+Vardi/05/Complementation, author = "Orna Kupferman and Moshe Y. Vardi", year = "2005", title = "Complementation Constructions for Nondeterministic Automata on Infinite Words", booktitle = "Tools and Algorithms for the Construction and Analysis of Systems", series = "Lecture Notes in Computer Science", volume = "3440", publisher = "Springer Berlin / Heidelberg", pages = "206--221", doi = "10.1007/978-3-540-31980-1\_14", ) @inproceedings(Loding/99/Optimal, author = "Christof L{\"{o}}ding", year = "1999", title = "Optimal Bounds for Transformations of omega-Automata", booktitle = "Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science", publisher = "Springer-Verlag", pages = "97--109", doi = "10.1007/3-540-46691-6\_8", ) @article(McNaughton/66/Testing, author = "Robert McNaughton", year = "1966", title = "Testing and Generating Infinite Sequences by a Finite Automaton", journal = "Information and Control", volume = "9", number = "5", pages = "521--530", doi = "10.1016/S0019-9958(66)80013-X", ) @misc(Michel/88/Complementation, author = "M. Michel", year = "1988", title = "Complementation is more difficult with automata on infinite words", note = "CNET", ) @article(Muller+Schupp/95/Simulating, author = "David E. Muller and Paul E. Schupp", year = "1995", title = "Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra", journal = "Theoretical Computer Science", volume = "141", number = "1-2", pages = "69--107", doi = "10.1016/0304-3975(94)00214-4", ) @inproceedings(Piterman/06/From, author = "N. Piterman", year = "2006", title = "From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata", booktitle = "21st Annual IEEE Symposium on Logic in Computer Science", pages = "255--264", doi = "10.1109/LICS.2006.28", ) @article(Rabin+Scott/59/Finite, author = "M. O. Rabin and D. Scott", year = "1959", title = "Finite automata and their decision problems", journal = "IBM Journal of Research and Development", volume = "3", pages = "114--125", doi = "10.1147/rd.32.0114", ) @inproceedings(Safra/88/Complexity, author = "S. Safra", year = "1988", title = "On the complexity of omega -automata", booktitle = "Proceedings of the 29th Annual Symposium on Foundations of Computer Science", publisher = "IEEE Computer Society", pages = "319--327", doi = "10.1109/SFCS.1988.21948", ) @inproceedings(Safra+Vardi/89/Omega, author = "S. Safra and M. Y. Vardi", year = "1989", title = "On $\omega $-automata and temporal logic", booktitle = "Proceedings of the 21st annual ACM symposium on Theory of computing (STOC'89)", publisher = "ACM", pages = "127--137", doi = "10.1145/73007.73019", ) @inproceedings(Safra/92/Exponential, author = "Shmuel Safra", year = "1992", title = "Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract)", booktitle = "Proceedings of the 24th annual ACM symposium on Theory of computing (STOC'92)", pages = "275--282", doi = "10.1145/129712.129739", ) @inproceedings(Schewe/09/Buchi, author = "Sven Schewe", year = "2009", title = "B{\"u}chi Complementation Made Tight", booktitle = "Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)", pages = "661--672", doi = "10.4230/LIPIcs.STACS.2009.1854", ) @inproceedings(Schewe/09/Tighter, author = "Sven Schewe", year = "2009", title = "Tighter Bounds for the Determinization of B{\"u}chi Automata", booktitle = "Proceedings of the 12th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2009)", pages = "167--181", ) @incollection(Schwoon/2002/Determinization, author = "Stefan Schwoon", year = "2002", title = "Determinization and Complementation of Streett Automata", booktitle = "Automata Logics, and Infinite Games", series = "Lecture Notes in Computer Science", volume = "2500", publisher = "Springer Berlin / Heidelberg", pages = "257--264", doi = "10.1007/3-540-36387-4\_5", ) @inproceedings(Vardi/07/Buchi, author = "Moshe Y. Vardi", year = "2007", title = "The {B\"{u}chi} complementation saga", booktitle = "Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS 2007)", publisher = "Springer-Verlag", pages = "12--22", doi = "10.1007/978-3-540-70918-3\_2", ) @inproceedings(Yan/06/Lower, author = "Qiqi Yan", year = "2006", title = "Lower Bounds for Complementation of $\omega $-Automata Via the Full Automata Technique", booktitle = "Proceedings of the 33rd Internatilonal Collogquium on Automata, Languages and Programming (ICALP 2006)", pages = "589--600", doi = "10.1007/11787006\_50", )