{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T15:30:59Z","timestamp":1743089459261,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031787089"},{"type":"electronic","value":"9783031787096"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-78709-6_4","type":"book-chapter","created":{"date-parts":[[2025,2,1]],"date-time":"2025-02-01T04:49:13Z","timestamp":1738385353000},"page":"67-88","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Easy Complementation of\u00a0History-Deterministic B\u00fcchi Automata"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8138-9406","authenticated-orcid":false,"given":"Bader","family":"Abu Radi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4699-6117","authenticated-orcid":false,"given":"Orna","family":"Kupferman","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9225-2325","authenticated-orcid":false,"given":"Ofer","family":"Leshkowitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,1]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Aminof, B., Kupferman, O., Lampert, R.: Reasoning about online algorithms with weighted automata. In: Proceedings 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 835\u2013844 (2010)","DOI":"10.1137\/1.9781611973068.91"},{"key":"4_CR2","unstructured":"Bagnol, M., Kuperberg, D.: B\u00fcchi good-for-games automata are efficiently recognizable. In: Proceedings 38th Conference on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, vol. 122, pp. 16:1\u201316:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-642-39212-2_11","volume-title":"Automata, Languages, and Programming","author":"U Boker","year":"2013","unstructured":"Boker, U., Kuperberg, D., Kupferman, O., Skrzypczak, M.: Nondeterminism in the presence of a diverse or unknown future. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7966, pp. 89\u2013100. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39212-2_11"},{"key":"4_CR4","unstructured":"Boker, U., Kupferman, O., Skrzypczak, M.: How deterministic are Good-For-Games automata? In: Proceedings 37th Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 93, pp. 18:1\u201318:14. Leibniz International Proceedings in Informatics (LIPIcs) (2017)"},{"issue":"1","key":"4_CR5","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/3584676.3584682","volume":"10","author":"U Boker","year":"2023","unstructured":"Boker, U., Lehtinen, K.: When a little nondeterminism goes a long way: an introduction to history-determinism. ACM SIGLOG News 10(1), 177\u2013196 (2023)","journal-title":"ACM SIGLOG News"},{"key":"4_CR6","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Proceedings International Congress on Logic, Method, and Philosophy of Science, 1960, pp. 1\u201312. Stanford University Press (1962)"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-642-02930-1_12","volume-title":"Automata, Languages and Programming","author":"T Colcombet","year":"2009","unstructured":"Colcombet, T.: The theory of stabilisation monoids and regular cost functions. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 139\u2013150. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02930-1_12"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Esparza, J., Kret\u00ednsk\u00fd, J., Sickert, S.: One theorem to rule them all: a unified translation of LTL into $$\\omega $$-automata. In: Proceedings 33rd IEEE Symposium on Logic in Computer Science, pp. 384\u2013393 (2018)","DOI":"10.1145\/3209108.3209161"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/11874683_26","volume-title":"Computer Science Logic","author":"TA Henzinger","year":"2006","unstructured":"Henzinger, T.A., Piterman, N.: Solving games without determinization. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 395\u2013410. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11874683_26"},{"issue":"2","key":"4_CR10","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1006\/inco.1997.2624","volume":"133","author":"CS Jutla","year":"1997","unstructured":"Jutla, C.S.: Determinization and memoryless winning strategies. Inf. Comput. 133(2), 117\u2013134 (1997)","journal-title":"Inf. Comput."},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Klarlund, N.: Progress measures, immediate determinacy, and a subset construction for tree automata. In: Proceedings 7th IEEE Symposium on Logic in Computer Science, pp. 382\u2013393. IEEE Computer Society (1992)","DOI":"10.1109\/LICS.1992.185550"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Kuperberg, D., Skrzypczak, M.: On determinisation of good-for-games automata. In: Proceedings 42nd International Colloquium on Automata, Languages, and Programming, pp. 299\u2013310 (2015)","DOI":"10.1007\/978-3-662-47666-6_24"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Kupferman, O.: Automata theory and model checking. In: Handbook of Model Checking, pp. 107\u2013151. Springer (2018)","DOI":"10.1007\/978-3-319-10575-8_4"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Kupferman, O.: Using the past for resolving the future. Front. Comput. Sci. 4 (2022)","DOI":"10.3389\/fcomp.2022.1114625"},{"issue":"1\u20133","key":"4_CR15","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.apal.2005.06.009","volume":"138","author":"O Kupferman","year":"2006","unstructured":"Kupferman, O., Safra, S., Vardi, M.Y.: Relating word and tree automata. Ann. Pure Appl. Logic 138(1\u20133), 126\u2013146 (2006)","journal-title":"Ann. Pure Appl. Logic"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Kupferman, O., Vardi, M.Y.: Safraless decision procedures. In: Proceedings 46th IEEE Symposium on Foundations of Computer Science, pp. 531\u2013540 (2005)","DOI":"10.1109\/SFCS.2005.66"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/BF01691063","volume":"3","author":"LH Landweber","year":"1969","unstructured":"Landweber, L.H.: Decision problems for $$\\omega $$-automata. Math. Syst. Theory 3, 376\u2013384 (1969)","journal-title":"Math. Syst. Theory"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Niwinski, D., Walukiewicz, I.: Relating hierarchies of word and tree automata. In: Proceedings 15th Symposium on Theoretical Aspects of Computer Science. LNCS, vol. 1373. Springer (1998)","DOI":"10.1007\/BFb0028571"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 115\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of $$\\omega $$-automata. In: Proceedings 29th IEEE Symposium on Foundations of Computer Science, pp. 319\u2013327 (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"issue":"1","key":"4_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1994.1092","volume":"115","author":"MY Vardi","year":"1994","unstructured":"Vardi, M.Y., Wolper, P.: Reasoning about infinite computations. Inf. Comput. 115(1), 1\u201337 (1994)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Automated Technology for Verification and Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-78709-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,1]],"date-time":"2025-02-01T04:49:31Z","timestamp":1738385371000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-78709-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031787089","9783031787096"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-78709-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"1 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ATVA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Automated Technology for Verification and Analysis","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kyoto","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 October 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 October 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"atva2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}