{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T08:26:25Z","timestamp":1746001585802},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662445211"},{"type":"electronic","value":"9783662445228"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44522-8_42","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:12:23Z","timestamp":1407838343000},"page":"499-510","source":"Crossref","is-referenced-by-count":3,"title":["Tight Bounds for Complementing Parity Automata"],"prefix":"10.1007","author":[{"given":"Sven","family":"Schewe","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Varghese","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"42_CR1","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Proc. of the Int. Congress on Logic, Methodology, and Philosophy of Science 1960, pp. 1\u201311 (1962)"},{"key":"42_CR2","unstructured":"Cai, Y., Zhang, T.: A tight lower bound for streett complementation. In: Proc. of FSTTCS 2011. LIPIcs, vol.\u00a013, pp. 339\u2013350 (2011)"},{"key":"42_CR3","unstructured":"Cai, Y., Zhang, T.: Tight upper bounds for streett and parity complementation. In: Proc. of CSL 2011. LIPIcs, vol.\u00a012, pp. 112\u2013128 (2011)"},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Cai, Y., Zhang, T., Luo, H.: An improved lower bound for the complementation of rabin automata. In: Proc. of LICS 2009 (2009)","DOI":"10.1109\/LICS.2009.13"},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"Duret-Lutz, A.: Ltl translation improvements in spot. In: Proc. of VECoS 2011, pp. 72\u201383. British Computer Society (2011)","DOI":"10.14236\/ewic\/VECOS2011.8"},{"issue":"4","key":"42_CR6","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\u2013867 (2006)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"2","key":"42_CR7","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 Transactions on Computational Logic\u00a02(2), 408\u2013429 (2001)","journal-title":"ACM Transactions on Computational Logic"},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Kurshan, R.P.: Computer-aided verification of coordinating processes: the aut-omata-theoretic approach. Princeton University Press (1994)","DOI":"10.1515\/9781400864041"},{"key":"42_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/3-540-46691-6_8","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"C. L\u00f6ding","year":"1999","unstructured":"L\u00f6ding, C.: Optimal bounds for transformations of \u03c9-automata. In: Pandu Rangan, C., Raman, V., Sarukkai, S. (eds.) FST TCS 1999. LNCS, vol.\u00a01738, pp. 97\u2013121. Springer, Heidelberg (1999)"},{"key":"42_CR10","unstructured":"Michel, M.: Complementation is more difficult with automata on infinite words. Technical report, CNET, Paris (1988) (manuscript)"},{"issue":"3","key":"42_CR11","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(86)90136-2","volume":"47","author":"J.-P. P\u00e9cuchet","year":"1986","unstructured":"P\u00e9cuchet, J.-P.: On the complementation of B\u00fcchi automata. TCS\u00a047(3), 95\u201398 (1986)","journal-title":"TCS"},{"key":"42_CR12","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 3(3:5) (2007)","DOI":"10.2168\/LMCS-3(3:5)2007"},{"key":"42_CR13","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":"42_CR14","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of \u03c9-automata. In: Proc. of FOCS 1988, pp. 319\u2013327 (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Safra, S.: Exponential determinization for omega-automata with strong-fairness acceptance condition (extended abstract). In: Proc. of STOC 1992, pp. 275\u2013282 (1992)","DOI":"10.1145\/129712.129739"},{"key":"42_CR16","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Non-determinism and the size of two-way automata. In: Proc. of STOC 1978, pp. 274\u2013286. ACM Press (1978)","DOI":"10.1145\/800133.804357"},{"key":"42_CR17","unstructured":"Schewe, S.: B\u00fcchi complementation made tight. In: Proc. of STACS 2009. LIPIcs, vol.\u00a03, pp. 661\u2013672 (2009)"},{"key":"42_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-642-00596-1_13","volume-title":"Foundations of Software Science and Computational Structures","author":"S. Schewe","year":"2009","unstructured":"Schewe, S.: Tighter bounds for the determinisation of B\u00fcchi automata. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol.\u00a05504, pp. 167\u2013181. Springer, Heidelberg (2009)"},{"key":"42_CR19","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":"42_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-540-71410-1_10","volume-title":"Logic-Based Program Synthesis and Transformation","author":"S. Schewe","year":"2007","unstructured":"Schewe, S., Finkbeiner, B.: Synthesis of asynchronous systems. In: Puebla, G. (ed.) LOPSTR 2006. LNCS, vol.\u00a04407, pp. 127\u2013142. Springer, Heidelberg (2007)"},{"key":"42_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-642-33386-6_5","volume-title":"Automated Technology for Verification and Analysis","author":"S. Schewe","year":"2012","unstructured":"Schewe, S., Varghese, T.: Tight bounds for the determinisation and complementation of generalised B\u00fcchi automata. In: Chakraborty, S., Mukund, M. (eds.) ATVA 2012. LNCS, vol.\u00a07561, pp. 42\u201356. Springer, Heidelberg (2012)"},{"key":"42_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1007\/978-3-662-44522-8_41","volume-title":"MFCS 2014, Part I","author":"S. Schewe","year":"2014","unstructured":"Schewe, S., Varghese, T.: Determinising parity automata. In: Csuhaj-Varj\u00fa, E., et al. (eds.) MFCS 2014, Part I. LNCS, vol.\u00a08634, pp. 486\u2013498. Springer, Heidelberg (2014)"},{"issue":"3","key":"42_CR23","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(3), 217\u2013239 (1987)","journal-title":"Theoretical Computer Science"},{"key":"42_CR24","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Complementation of B\u00fcchi automata revisited. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 109\u2013122 (1999)","DOI":"10.1007\/978-3-642-60207-8_10"},{"key":"42_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/978-3-642-39799-8_62","volume-title":"Computer Aided Verification","author":"M.-H. Tsai","year":"2013","unstructured":"Tsai, M.-H., Tsay, Y.-K., Hwang, Y.-S.: GOAL for games, omega-automata, and logics. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol.\u00a08044, pp. 883\u2013889. Springer, Heidelberg (2013)"},{"key":"42_CR26","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":"M.Y. Vardi","year":"2007","unstructured":"Vardi, M.Y.: The B\u00fcchi complementation saga. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 12\u201322. Springer, Heidelberg (2007)"},{"key":"42_CR27","doi-asserted-by":"crossref","unstructured":"Wilke, T.: Alternating tree automata, parity games, and modal \u03bc-calculus. Bulletin of the Belgian Mathematical Society 8(2) (May 2001)","DOI":"10.36045\/bbms\/1102714178"},{"key":"42_CR28","doi-asserted-by":"crossref","unstructured":"Yan, Q.: Lower bounds for complementation of \u03c9-automata via the full automata technique. Journal of Logical Methods in Computer Science 4(1:5) (2008)","DOI":"10.2168\/LMCS-4(1:5)2008"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44522-8_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,23]],"date-time":"2020-08-23T04:04:48Z","timestamp":1598155488000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44522-8_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662445211","9783662445228"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44522-8_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}