{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T05:51:29Z","timestamp":1742968289855,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031223365"},{"type":"electronic","value":"9783031223372"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22337-2_9","type":"book-chapter","created":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:08:41Z","timestamp":1672222121000},"page":"185-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards a\u00a0Grand Unification of\u00a0B\u00fcchi Complementation Constructions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0661-5773","authenticated-orcid":false,"given":"Moshe Y.","family":"Vardi","sequence":"first","affiliation":[]},{"given":"Seth","family":"Fogarty","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7301-9234","authenticated-orcid":false,"given":"Yong","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5960-1615","authenticated-orcid":false,"given":"Yih-Kuen","family":"Tsay","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,29]]},"reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-642-14295-6_14","volume-title":"Computer Aided Verification","author":"PA Abdulla","year":"2010","unstructured":"Abdulla, P.A., et al.: Simulation subsumption in Ramsey-based B\u00fcchi automata universality and inclusion testing. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol. 6174, pp. 132\u2013147. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14295-6_14"},{"key":"9_CR2","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":"PA Abdulla","year":"2011","unstructured":"Abdulla, P.A., et al.: Advanced Ramsey-based B\u00fcchi automata inclusion testing. In: Katoen, J.-P., K\u00f6nig, B. (eds.) CONCUR 2011. LNCS, vol. 6901, pp. 187\u2013202. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23217-6_13"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Allred, J.D., Ultes-Nitsche, U.: A simple and optimal complementation algorithm for B\u00fcchi automata. In: Dawar, A., Gr\u00e4del, E. (ed.) LICS, pp. 46\u201355. ACM (2018)","DOI":"10.1145\/3209108.3209138"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2016.07.031","volume":"650","author":"D Angluin","year":"2016","unstructured":"Angluin, D., Fisman, D.: Learning regular omega languages. Theor. Comput. Sci. 650, 57\u201372 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-642-28729-9_10","volume-title":"Foundations of Software Science and Computational Structures","author":"S Breuers","year":"2012","unstructured":"Breuers, S., L\u00f6ding, C., Olschewski, J.: Improved Ramsey-based B\u00fcchi complementation. In: Birkedal, L. (ed.) FoSSaCS 2012. LNCS, vol. 7213, pp. 150\u2013164. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28729-9_10"},{"key":"9_CR6","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Proceedings of International Congress on Logic, Method, and Philosophy of Science, pp. 1\u201312. Stanford University Press (1962)"},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/3-540-58027-1_27","volume-title":"Mathematical Foundations of Programming Semantics","author":"H Calbrix","year":"1994","unstructured":"Calbrix, H., Nivat, M., Podelski, A.: Ultimately periodic words of rational $$\\omega $$-languages. In: Brookes, S., Main, M., Melton, A., Mislove, M., Schmidt, D. (eds.) MFPS 1993. LNCS, vol. 802, pp. 554\u2013566. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58027-1_27"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-030-34175-6_23","volume-title":"Programming Languages and Systems","author":"Y-F Chen","year":"2019","unstructured":"Chen, Y.-F., Havlena, V., Leng\u00e1l, O.: Simulations in rank-based B\u00fcchi automata complementation. In: Lin, A.W. (ed.) APLAS 2019. LNCS, vol. 11893, pp. 447\u2013467. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34175-6_23"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/3-540-16078-7_62","volume-title":"STACS 86","author":"E Allen Emerson","year":"1986","unstructured":"Allen Emerson, E., Lei, C.-L.: Temporal reasoning under generalized fairness constraints. In: Monien, B., Vidal-Naquet, G. (eds.) STACS 1986. LNCS, vol. 210, pp. 21\u201336. Springer, Heidelberg (1986). https:\/\/doi.org\/10.1007\/3-540-16078-7_62"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/3-540-45319-9_29","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"K Fisler","year":"2001","unstructured":"Fisler, K., Fraer, R., Kamhi, G., Vardi, M.Y., Yang, Z.: Is there a best symbolic cycle-detection algorithm? In: Margaria, T., Yi, W. (eds.) TACAS 2001. LNCS, vol. 2031, pp. 420\u2013434. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45319-9_29"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.ic.2014.12.021","volume":"245","author":"S Fogarty","year":"2015","unstructured":"Fogarty, S., Kupferman, O., Vardi, M.Y., Wilke, T.: Profile trees for B\u00fcchi word automata, with application to determinization. Inf. Comput. 245, 136\u2013151 (2015)","journal-title":"Inf. Comput."},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Fogarty, S., Kupferman, O., Wilke, T., Vardi, M.Y.: Unifying B\u00fcchi complementation constructions. Log. Methods Comput. Sci. 9(1), 1\u201326 (2013)","DOI":"10.2168\/LMCS-9(1:13)2013"},{"key":"9_CR13","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. 6015, pp. 205\u2013220. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12002-2_17"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Fogarty, S., Vardi, M.Y.: B\u00fcchi complementation and size-change termination. Log. Methods Comput. Sci. 8(1), 1\u201333 (2012)","DOI":"10.2168\/LMCS-8(1:13)2012"},{"issue":"4","key":"9_CR15","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. Int. J. Found. Comput. Sci. 17(4), 851\u2013868 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-39724-3_10","volume-title":"Correct Hardware Design and Verification Methods","author":"S Gurumurthy","year":"2003","unstructured":"Gurumurthy, S., Kupferman, O., Somenzi, F., Vardi, M.Y.: On complementing nondeterministic B\u00fcchi automata. In: Geist, D., Tronci, E. (eds.) CHARME 2003. LNCS, vol. 2860, pp. 96\u2013110. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39724-3_10"},{"key":"9_CR17","unstructured":"Havlena, V., Leng\u00e1l, O.: Reducing (to) the ranks: efficient rank-based B\u00fcchi automata complementation (technical report). CoRR, abs\/2010.07834 (2020)"},{"key":"9_CR18","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"JE Hopcroft","year":"2000","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, 2nd edn. Addison-Wesley, Reading (2000)","edition":"2"},{"key":"9_CR19","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. LNCS, vol. 5125, pp. 724\u2013735. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_59"},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-642-04761-9_18","volume-title":"Automated Technology for Verification and Analysis","author":"H Karmarkar","year":"2009","unstructured":"Karmarkar, H., Chakraborty, S.: On minimal odd rankings for B\u00fcchi complementation. In: Liu, Z., Ravn, A.P. (eds.) ATVA 2009. LNCS, vol. 5799, pp. 228\u2013243. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04761-9_18"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Klarlund, N.: Progress measures for complementation of omega-automata with applications to temporal logic. In: FOCS, pp. 358\u2013367. IEEE Computer Society (1991)","DOI":"10.1109\/SFCS.1991.185391"},{"issue":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1023\/A:1011254632723","volume":"19","author":"O Kupferman","year":"2001","unstructured":"Kupferman, O., Vardi, M.Y.: Model checking of safety properties. Formal Methods Syst. Des. 19(3), 291\u2013314 (2001)","journal-title":"Formal Methods Syst. Des."},{"issue":"3","key":"9_CR23","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1145\/377978.377993","volume":"2","author":"O Kupferman","year":"2001","unstructured":"Kupferman, O., Vardi, M.Y.: Weak alternating automata are not that weak. ACM Trans. Comput. Log. 2(3), 408\u2013429 (2001)","journal-title":"ACM Trans. Comput. Log."},{"key":"9_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-030-90870-6_25","volume-title":"Formal Methods","author":"Y Li","year":"2021","unstructured":"Li, Y., Tsay, Y.-K., Turrini, A., Vardi, M.Y., Zhang, L.: Congruence relations for B\u00fcchi automata. In: Huisman, M., P\u0103s\u0103reanu, C., Zhan, N. (eds.) FM 2021. LNCS, vol. 13047, pp. 465\u2013482. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-90870-6_25"},{"key":"9_CR25","unstructured":"L\u00f6ding, C., Pirogov, A.: Determinization of B\u00fcchi automata: unifying the approaches of Safra and Muller-Schupp. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) ICALP. LIPIcs, vol. 132, pp. 120:1\u2013120:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"1","key":"9_CR26","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0304-3975(96)00312-X","volume":"183","author":"O Maler","year":"1997","unstructured":"Maler, O., Staiger, L.: On syntactic congruences for omega-languages. Theor. Comput. Sci. 183(1), 93\u2013112 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR27","unstructured":"Michel, M.: Complementation is more difficult with automata on infinite words. Technical report, CNET, Paris (Manuscript) (1988)"},{"key":"9_CR28","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0304-3975(84)90049-5","volume":"32","author":"S Miyano","year":"1984","unstructured":"Miyano, S., Hayashi, T.: Alternating finite automata on omega-words. Theor. Comput. Sci. 32, 321\u2013330 (1984)","journal-title":"Theor. Comput. Sci."},{"issue":"1 &2","key":"9_CR29","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(94)00214-4","volume":"141","author":"DE 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. Theor. Comput. Sci. 141(1 &2), 69\u2013107 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR30","unstructured":"Myhill, J.: Finite automata and the representation of events. Technical report, WADD TR-57-624, pp. 112\u2013137 (1957)"},{"key":"9_CR31","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformations. Am. Math. Soc. 9, 541\u2013544 (1958)","journal-title":"Am. Math. Soc."},{"key":"9_CR32","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of $$\\omega $$-automata. In: FOCS, pp. 319\u2013327. IEEE (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"key":"9_CR33","unstructured":"Schewe, S.: B\u00fcchi complementation made tight. In: STACS. LIPIcs, vol. 3, pp. 661\u2013672. Schloss Dagstuhl, Germany (2009)"},{"issue":"2\u20133","key":"9_CR34","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0304-3975(87)90008-9","volume":"49","author":"AP Sistla","year":"1987","unstructured":"Sistla, A.P., Vardi, M.Y., Wolper, P.: The complementation problem for B\u00fcchi automata with applications to temporal logic. Theor. Comput. Sci. 49(2\u20133), 217\u2013237 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR35","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Automata on infinite objects. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pp. 133\u2013191. Elsevier and MIT Press (1990)","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"9_CR36","doi-asserted-by":"crossref","unstructured":"Tsai, M.-H., Fogarty, S., Vardi, M.Y., Tsay, Y.-K.: State of B\u00fcchi complementation. Log. Methods Comput. Sci. 10(4), 1\u201327 (2014)","DOI":"10.2168\/LMCS-10(4:13)2014"},{"key":"9_CR37","unstructured":"Vardi, M.Y.: Expected properties of set partitions. Technical report, The Weizmann Institute of Science (1980)"},{"issue":"1\u20132","key":"9_CR38","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0168-0072(91)90066-U","volume":"51","author":"MY Vardi","year":"1991","unstructured":"Vardi, M.Y.: Verification of concurrent programs: the automata-theoretic framework. Ann. Pure Appl. Log. 51(1\u20132), 79\u201398 (1991)","journal-title":"Ann. Pure Appl. Log."},{"key":"9_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/978-3-540-70918-3_2","volume-title":"STACS 2007","author":"MY Vardi","year":"2007","unstructured":"Vardi, M.Y.: The B\u00fcchi complementation Saga. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 12\u201322. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-70918-3_2"},{"key":"9_CR40","unstructured":"Vardi, M.Y., Wolper, P.: An automata-theoretic approach to automatic program verification (preliminary report). In: LICS, pp. 332\u2013344. IEEE (1986)"},{"key":"9_CR41","doi-asserted-by":"crossref","unstructured":"Yan, Q.: Lower bounds for complementation of $$\\omega $$-automata via the full automata technique. Log. Methods Comput. Sci. 4(1:5), 1\u201320 (2008)","DOI":"10.2168\/LMCS-4(1:5)2008"}],"container-title":["Lecture Notes in Computer Science","Principles of Systems Design"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22337-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T02:54:55Z","timestamp":1728615295000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22337-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031223365","9783031223372"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22337-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 December 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}