{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T18:21:14Z","timestamp":1784830874332,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642287282","type":"print"},{"value":"9783642287299","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28729-9_10","type":"book-chapter","created":{"date-parts":[[2012,3,22]],"date-time":"2012-03-22T20:47:40Z","timestamp":1332449260000},"page":"150-164","source":"Crossref","is-referenced-by-count":14,"title":["Improved Ramsey-Based B\u00fcchi Complementation"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Breuers","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christof","family":"L\u00f6ding","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00f6rg","family":"Olschewski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-642-23217-6_13","volume-title":"CONCUR 2011 \u2013 Concurrency Theory","author":"P.A. Abdulla","year":"2011","unstructured":"Abdulla, P.A., Chen, Y.-F., Clemente, L., Hol\u00edk, L., Hong, C.-D., Mayr, R., Vojnar, T.: Advanced Ramsey-based B\u00fcchi Automata Inclusion Testing. In: Katoen, J.-P., K\u00f6nig, B. (eds.) CONCUR 2011 \u2013 Concurrency Theory. LNCS, vol.\u00a06901, pp. 187\u2013202. Springer, Heidelberg (2011)"},{"key":"10_CR2","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Logic, Methodology and Philosophy of Science, pp. 1\u201311. Stanford Univerity Press (1962)"},{"key":"10_CR3","unstructured":"Fogarty, S., Kupferman, O., Vardi, M.Y., Wilke, T.: Unifying B\u00fcchi complementation constructions. In: CSL (2011)"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-642-12002-2_17","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"S. Fogarty","year":"2010","unstructured":"Fogarty, S., Vardi, M.Y.: Efficient B\u00fcchi Universality Checking. In: Esparza, J., Majumdar, R. (eds.) TACAS 2010. LNCS, vol.\u00a06015, pp. 205\u2013220. Springer, Heidelberg (2010)"},{"issue":"4","key":"10_CR5","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(4), 851\u2013868 (2006)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1007\/978-3-540-70575-8_59","volume-title":"Automata, Languages and Programming","author":"D. K\u00e4hler","year":"2008","unstructured":"K\u00e4hler, D., Wilke, T.: Complementation, Disambiguation, and Determinization of B\u00fcchi Automata Unified. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 724\u2013735. Springer, Heidelberg (2008)"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Klarlund, N.: Progress measures for complementation of \u03c9-automata with applications to temporal logic. In: FOCS, pp. 358\u2013367. IEEE Computer Society (1991)","DOI":"10.1109\/SFCS.1991.185391"},{"key":"10_CR8","unstructured":"Michel, M.: Complementation is more difficult with automata on infinite words. Technical report, CNET, Paris (1988)"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Piterman, N.: From nondeterministic B\u00fcchi and Streett automata to deterministic parity automata. Logical Methods in Computer Science\u00a03(3) (2007)","DOI":"10.2168\/LMCS-3(3:5)2007"},{"issue":"1","key":"10_CR10","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","volume":"2","author":"F.P. Ramsey","year":"1930","unstructured":"Ramsey, F.P.: On a problem of formal logic. Proceedings of the London Mathematical Society\u00a02(1), 264 (1930)","journal-title":"Proceedings of the London Mathematical Society"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of \u03c9-automata. In: FOCS, pp. 319\u2013327. IEEE (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"key":"10_CR12","unstructured":"Schewe, S.: B\u00fcchi complementation made tight. In: STACS. LIPIcs, vol.\u00a03, pp. 661\u2013672. Schloss Dagstuhl (2009)"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0304-3975(87)90008-9","volume":"49","author":"A.P. Sistla","year":"1987","unstructured":"Sistla, A.P., Vardi, M.Y., Wolper, P.: The complementation problem for B\u00fcchi automata with applications to temporal logic. Theoretical Computer Science\u00a049, 217\u2013237 (1987)","journal-title":"Theoretical Computer Science"},{"key":"10_CR14","series-title":"Formal Models and Semantics","first-page":"133","volume-title":"Handbook of Theoretical Computer Science","author":"W. Thomas","year":"1990","unstructured":"Thomas, W.: Automata on infinite objects. In: Handbook of Theoretical Computer Science. Formal Models and Semantics, vol.\u00a0B, pp. 133\u2013192. Elsevier Science Publishers, Amsterdam (1990)"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-642-18098-9_28","volume-title":"Implementation and Application of Automata","author":"M.-H. Tsai","year":"2011","unstructured":"Tsai, M.-H., Fogarty, S., Vardi, M.Y., Tsay, Y.-K.: State of B\u00fcchi Complementation. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol.\u00a06482, pp. 261\u2013271. Springer, Heidelberg (2011)"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Yan, Q.: Lower bounds for complementation of \u03c9-automata via the full automata technique. Logical Methods in Computer Science\u00a04(1) (2008)","DOI":"10.2168\/LMCS-4(1:5)2008"},{"key":"10_CR17","unstructured":"http:\/\/www.automata.rwth-aachen.de\/research\/Alekto\/"}],"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-28729-9_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T18:49:28Z","timestamp":1742755768000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28729-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642287282","9783642287299"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28729-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}