{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:50Z","timestamp":1760202770654,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":17,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,9]],"date-time":"2018-07-09T00:00:00Z","timestamp":1531094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,9]]},"DOI":"10.1145\/3209108.3209138","type":"proceedings-article","created":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T12:14:43Z","timestamp":1530101683000},"page":"46-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["A Simple and Optimal Complementation Algorithm for B\u00fcchi Automata"],"prefix":"10.1145","author":[{"given":"Joel D.","family":"Allred","sequence":"first","affiliation":[{"name":"Diffblue Ltd, Oxford, UK"}]},{"given":"Ulrich","family":"Ultes-Nitsche","sequence":"additional","affiliation":[{"name":"University of Fribourg, Fribourg, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2018,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the International Congress on Logic, Methodology and Philosophy of Science","author":"B\u00fcchi J. R.","year":"1962","unstructured":"J. R. B\u00fcchi . 1962 . On a Decision Method in Restricted Second Order Arithmetic . In Proceedings of the International Congress on Logic, Methodology and Philosophy of Science 1960, E. Nagel et al. (Eds.). Stanford University Press, 1--11. J. R. B\u00fcchi. 1962. On a Decision Method in Restricted Second Order Arithmetic. In Proceedings of the International Congress on Logic, Methodology and Philosophy of Science 1960, E. Nagel et al. (Eds.). Stanford University Press, 1--11."},{"key":"e_1_3_2_1_2_1","volume-title":"26th International Conference on Concurrency Theory, CONCUR 2015","author":"Fisman Dana","year":"2015","unstructured":"Dana Fisman and Yoad Lustig . 2015 . A Modular Approach for B\u00fcchi Determinization . In 26th International Conference on Concurrency Theory, CONCUR 2015 , Madrid, Spain, September 1.4 , 2015. 368--382. Dana Fisman and Yoad Lustig. 2015. A Modular Approach for B\u00fcchi Determinization. In 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, September 1.4, 2015. 368--382."},{"key":"e_1_3_2_1_3_1","volume-title":"Vardi","author":"Fogarty Seth","year":"2013","unstructured":"Seth Fogarty , Orna Kupferman , Thomas Wilke , and Moshe Y . Vardi . 2013 . Unifying B\u00fcchi Complementation Constructions. Logical Methods in Computer Science 9, 1 (2013). Seth Fogarty, Orna Kupferman, Thomas Wilke, and Moshe Y. Vardi. 2013. Unifying B\u00fcchi Complementation Constructions. Logical Methods in Computer Science 9, 1 (2013)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989826"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_59"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/377978.377993"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the 3rd International Conference on Developments in Language Theory (DLT'97)","author":"Nie\u00dfner Frank","year":"1998","unstructured":"Frank Nie\u00dfner , Ulrich Nitsche , and Peter Ochsenschl\u00e4ger . 1998 . Deterministic \u03c9-Regular Liveness Properties . In Proceedings of the 3rd International Conference on Developments in Language Theory (DLT'97) , Symeon Bozapalidis (Ed.). Thessaloniki, Greece, 237--247. Frank Nie\u00dfner, Ulrich Nitsche, and Peter Ochsenschl\u00e4ger. 1998. Deterministic \u03c9-Regular Liveness Properties. In Proceedings of the 3rd International Conference on Developments in Language Theory (DLT'97), Symeon Bozapalidis (Ed.). Thessaloniki, Greece, 237--247."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.28"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21948"},{"key":"e_1_3_2_1_10_1","volume-title":"Susanne Albers and Jean-Yves Marion (Eds.)","volume":"3","author":"Schewe Sven","year":"2009","unstructured":"Sven Schewe . 2009 . B\u00fcchi Complementation Made Tight. In STAGS (LIPIcs) , Susanne Albers and Jean-Yves Marion (Eds.) , Vol. 3 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 661--672. Sven Schewe. 2009. B\u00fcchi Complementation Made Tight. In STAGS (LIPIcs), Susanne Albers and Jean-Yves Marion (Eds.), Vol. 3. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 661--672."},{"key":"e_1_3_2_1_11_1","unstructured":"J. Stirling. 1730. Methodus differentialis sive tractatus de summation et interpolation serierum infinitarium.  J. Stirling. 1730. Methodus differentialis sive tractatus de summation et interpolation serierum infinitarium."},{"volume-title":"Formal Models and Semantics (Handbook of Theoretical Computer Science), Jan van Leeuwen (Ed.)","author":"Thomas Wolfgang","key":"e_1_3_2_1_12_1","unstructured":"Wolfgang Thomas . 1990. Automata on Infinite Objects . In Formal Models and Semantics (Handbook of Theoretical Computer Science), Jan van Leeuwen (Ed.) , Vol. B. Elsevier, 133-- 191 . Wolfgang Thomas. 1990. Automata on Infinite Objects. In Formal Models and Semantics (Handbook of Theoretical Computer Science), Jan van Leeuwen (Ed.), Vol. B. Elsevier, 133--191."},{"key":"e_1_3_2_1_13_1","volume-title":"CIAA 2010","author":"Tsai Ming-Hsien","year":"2010","unstructured":"Ming-Hsien Tsai , Seth Fogarty , Moshe Y. Vardi , and Yih-Kuen Tsay . 2010 . State of B\u00fcchi Complementation. In Implementation and Application of Automata - 15th International Conference , CIAA 2010 , Winnipeg, MB, Canada , August 12-15, 2010. Revised Selected Papers (Lecture Notes in Computer Science), Michael Domaratzki and Kai Salomaa (Eds.), Vol. 6482. Springer, 261--271. Ming-Hsien Tsai, Seth Fogarty, Moshe Y. Vardi, and Yih-Kuen Tsay. 2010. State of B\u00fcchi Complementation. In Implementation and Application of Automata - 15th International Conference, CIAA 2010, Winnipeg, MB, Canada, August 12-15, 2010. Revised Selected Papers (Lecture Notes in Computer Science), Michael Domaratzki and Kai Salomaa (Eds.), Vol. 6482. Springer, 261--271."},{"key":"e_1_3_2_1_14_1","volume-title":"Lecture Notes in Computer Science","volume":"4424","author":"Tsay Yih-Kuen","year":"2007","unstructured":"Yih-Kuen Tsay , Yu-Fang Chen , Ming-Hsien Tsai , Kang-Nien Wu , and Wen-Chin Chan . 2007 . GOAL: A Graphical Tool for Manipulating B\u00fcchi Automata and Temporal Formulae. In Tools and Algorithms for the Construction and Analysis of Systems, Orna Grumberg and Michael Huth (Eds.) . Lecture Notes in Computer Science , Vol. 4424 . Springer Berlin Heidelberg, 466--471. Yih-Kuen Tsay, Yu-Fang Chen, Ming-Hsien Tsai, Kang-Nien Wu, and Wen-Chin Chan. 2007. GOAL: A Graphical Tool for Manipulating B\u00fcchi Automata and Temporal Formulae. In Tools and Algorithms for the Construction and Analysis of Systems, Orna Grumberg and Michael Huth (Eds.). Lecture Notes in Computer Science, Vol. 4424. Springer Berlin Heidelberg, 466--471."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.08.014"},{"key":"e_1_3_2_1_16_1","volume-title":"Empirical Performance Investigation of a B\u00fcchi Complementation Construction. Master thesis","author":"Weibel Daniel","year":"2015","unstructured":"Daniel Weibel . 2015. Empirical Performance Investigation of a B\u00fcchi Complementation Construction. Master thesis , University of Fribourg , Switzerland. ( 2015 ). Daniel Weibel. 2015. Empirical Performance Investigation of a B\u00fcchi Complementation Construction. Master thesis, University of Fribourg, Switzerland. (2015)."},{"key":"e_1_3_2_1_17_1","article-title":"Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique","volume":"4","author":"Yan Qiqi","year":"2008","unstructured":"Qiqi Yan . 2008 . Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique . Journal of Logical Methods in Computer Science 4 , 1 (2008), 20 pages. Qiqi Yan. 2008. Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique. Journal of Logical Methods in Computer Science 4, 1 (2008), 20 pages.","journal-title":"Journal of Logical Methods in Computer Science"}],"event":{"name":"LICS '18: 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"],"location":"Oxford United Kingdom","acronym":"LICS '18"},"container-title":["Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209138","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209108.3209138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:07Z","timestamp":1750212427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,9]]},"references-count":17,"alternative-id":["10.1145\/3209108.3209138","10.1145\/3209108"],"URL":"https:\/\/doi.org\/10.1145\/3209108.3209138","relation":{},"subject":[],"published":{"date-parts":[[2018,7,9]]},"assertion":[{"value":"2018-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}