{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T21:33:39Z","timestamp":1762032819050},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642005954"},{"type":"electronic","value":"9783642005961"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-00596-1_13","type":"book-chapter","created":{"date-parts":[[2009,3,27]],"date-time":"2009-03-27T01:13:03Z","timestamp":1238116383000},"page":"167-181","source":"Crossref","is-referenced-by-count":43,"title":["Tighter Bounds for the Determinisation of B\u00fcchi Automata"],"prefix":"10.1007","author":[{"given":"Sven","family":"Schewe","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Proceedings of the International Congress on Logic, Methodology, and Philosophy of Science, 1960, Berkeley, California, USA, pp. 1\u201311. Stanford University Press (1962)"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.S.: Finite automata and their decision problems. IBM Journal of Research and Development\u00a03, 115\u2013125 (1959)","journal-title":"IBM Journal of Research and Development"},{"key":"13_CR3","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1109\/SFCS.1988.21948","volume-title":"Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS 1988)","author":"S. Safra","year":"1988","unstructured":"Safra, S.: On the complexity of \u03c9-automata. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS 1988), White Plains, New York, USA, pp. 319\u2013327. IEEE Computer Society Press, Los Alamitos (1988)"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(94)00214-4","volume":"141","author":"D.E. Muller","year":"1995","unstructured":"Muller, D.E., Schupp, P.E.: Simulating alternating tree automata by nondeterministic automata: new results and new proofs of the theorems of Rabin, McNaughton and Safra. Theoretical Computer Science\u00a0141, 69\u2013107 (1995)","journal-title":"Theoretical Computer Science"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Piterman, N.: From nondeterministic B\u00fcchi and Streett automata to deterministic parity automata. Journal of Logical Methods in Computer Science\u00a03 (2007)","DOI":"10.2168\/LMCS-3(3:5)2007"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/SWCT.1963.8","volume-title":"Proceedings of the 4th Annual Symposium on Switching Circuit Theory and Logical Design (FOCS 1963)","author":"D.E. Muller","year":"1963","unstructured":"Muller, D.E.: Infinite sequences and finite machines. In: Proceedings of the 4th Annual Symposium on Switching Circuit Theory and Logical Design (FOCS 1963), Chicago, Chicago, Illinois, USA, pp. 3\u201316. IEEE Computer Society Press, Los Alamitos (1963)"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R. McNaughton","year":"1966","unstructured":"McNaughton, R.: Testing and generating infinite sequences by a finite automaton. Information and Control\u00a09, 521\u2013530 (1966)","journal-title":"Information and Control"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Yan, Q.: Lower bounds for complementation of omega-automata via the full automata technique. Journal of Logical Methods in Computer Science\u00a04 (2008)","DOI":"10.2168\/LMCS-4(1:5)2008"},{"key":"13_CR9","unstructured":"Church, A.: Logic, arithmetic and automata. In: Proceedings of the International Congress of Mathematicians, Institut Mittag-Leffler, Djursholm, Sweden, 1962 (Stockholm 1963), 15\u201322 August, pp. 23\u201335 (1962)"},{"key":"13_CR10","first-page":"179","volume-title":"Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages (POPL 1989)","author":"A. Pnueli","year":"1989","unstructured":"Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages (POPL 1989), Austin, Texas, USA, pp. 179\u2013190. ACM Press, New York (1989)"},{"key":"13_CR11","first-page":"1","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"Rabin, M.O.: Decidability of second order theories and automata on infinite trees. Transaction of the American Mathematical Society\u00a0141, 1\u201335 (1969)","journal-title":"Transaction of the American Mathematical Society"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1090\/S0002-9947-1969-0280205-0","volume":"138","author":"J.R. B\u00fcchi","year":"1969","unstructured":"B\u00fcchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies. Transactions of the American Mathematical Society\u00a0138, 295\u2013311 (1969)","journal-title":"Transactions of the American Mathematical Society"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"166","DOI":"10.2307\/2271090","volume":"34","author":"J.R. B\u00fcchi","year":"1969","unstructured":"B\u00fcchi, J.R., Landweber, L.H.: Definability in the monadic second-order theory of successor. Journal of Symbolic Logic\u00a034, 166\u2013170 (1969)","journal-title":"Journal of Symbolic Logic"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Wilke, T.: Alternating tree automata, parity games, and modal \u03bc-calculus. Bulletin of the Belgian Mathematical Society\u00a08 (2001)","DOI":"10.36045\/bbms\/1102714178"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/3-540-15648-8_7","volume-title":"Logics of Programs","author":"E.A. Emerson","year":"1985","unstructured":"Emerson, E.A.: Automata, tableaux and temporal logics. In: Parikh, R. (ed.) Logic of Programs 1985. LNCS, vol.\u00a0193, pp. 79\u201388. Springer, Heidelberg (1985)"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/3-540-63166-6_7","volume-title":"Computer Aided Verification","author":"O. Kupferman","year":"1997","unstructured":"Kupferman, O., Vardi, M.: Module checking revisited. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol.\u00a01254, pp. 36\u201347. Springer, Heidelberg (1997)"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1109\/SFCS.1991.185392","volume-title":"Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991)","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, \u03bc-calculus and determinacy. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), San Juan, Puerto Rico, pp. 368\u2013377. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/11874683_39","volume-title":"Computer Science Logic","author":"S. Schewe","year":"2006","unstructured":"Schewe, S., Finkbeiner, B.: Satisfiability and finite model property for the alternating-time \u03bc-calculus. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 591\u2013605. Springer, Heidelberg (2006)"},{"key":"13_CR19","first-page":"60","volume-title":"Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC 1982)","author":"Y. Gurevich","year":"1982","unstructured":"Gurevich, Y., Harrington, L.: Trees, automata, and games. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC 1982), San Francisco, California, USA, pp. 60\u201365. ACM Press, New York (1982)"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Liu, W., Wang, J.: A tigher analysis of Piterman\u2019s B\u00fcchi determinization. Information Processing Letters (submitted, 2009)","DOI":"10.1016\/j.ipl.2009.04.022"},{"key":"13_CR21","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1002\/sapm1993893233","volume":"89","author":"N.M. Temme","year":"1993","unstructured":"Temme, N.M.: Asymptotic estimates of Stirling numbers. Studies in Applied Mathematics\u00a089, 233\u2013243 (1993)","journal-title":"Studies in Applied Mathematics"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1142\/S0129054106004145","volume":"17","author":"E. Friedgut","year":"2006","unstructured":"Friedgut, E., Kupferman, O., Vardi, M.Y.: B\u00fcchi complementation made tighter. International Journal of Foundations of Computer Science\u00a017, 851\u2013867 (2006)","journal-title":"International Journal of Foundations of Computer Science"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computational Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00596-1_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T03:48:46Z","timestamp":1589687326000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00596-1_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642005954","9783642005961"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00596-1_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}