{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T10:52:25Z","timestamp":1753354345381},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540418641"},{"type":"electronic","value":"9783540453154"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45315-6_18","type":"book-chapter","created":{"date-parts":[[2007,12,3]],"date-time":"2007-12-03T01:28:39Z","timestamp":1196645319000},"page":"276-286","source":"Crossref","is-referenced-by-count":23,"title":["On the Complexity of Parity Word Automata"],"prefix":"10.1007","author":[{"given":"Valerie","family":"King","sequence":"first","affiliation":[]},{"given":"Orna","family":"Kupferman","sequence":"additional","affiliation":[]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,3,23]]},"reference":[{"key":"18_CR1","series-title":"Lect Notes Comput Sci","volume-title":"Formal Methods in Computer Aided Design","author":"R. Bloem","year":"2000","unstructured":"R. Bloem, H.N. Gabow, and F. Somenzi. An algorithm for strongly connected component analysis in n log n symbolic steps. In Formal Methods in Computer Aided Design, Lecture Notes in Computer Science. Springer-Verlag, 2000."},{"key":"18_CR2","unstructured":"J.R. B\u00fcchi. On a decision method in restricted second order arithmetic. In Proc. Internat. Congr. Logic, Method. and Philos. Sci. 1960, pages 1\u201312, Stanford, 1962. Stanford University Press."},{"issue":"2","key":"18_CR3","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1145\/5397.5399","volume":"8","author":"E.M. Clarke","year":"1986","unstructured":"E.M. Clarke, E.A. Emerson, and A.P. Sistla. Automatic verification of finite-state concurrent systems using temporal logic specifications. ACM Transactions on Programming Languages and Systems, 8(2):244\u2013263, January 1986.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0022-0000(74)80051-6","volume":"8","author":"Y. Choueka","year":"1974","unstructured":"Y. Choueka. Theories of automata on \u03c9-tapes: A simplified approach. Journal of Computer and System Sciences, 8:117\u2013141, 1974.","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"E.A. Emerson and C. Jutla. The complexity of tree automata and logics of programs. In Proc. 29th IEEE Symp. on Foundations of Computer Science, pages 328\u2013337, White Plains, October 1988.","DOI":"10.1109\/SFCS.1988.21949"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"E.A. Emerson and C. Jutla. Tree automata, \u03bc-calculus and determinacy. In Proc. 32nd IEEE Symp. on Foundations of Computer Science, pages 368\u2013377, San Juan, October 1991.","DOI":"10.1109\/SFCS.1991.185392"},{"key":"18_CR7","series-title":"Lect Notes Comput Sci","first-page":"10","volume-title":"Proc. 5th Scandinavian Workshop on Algorithm Theory","author":"M. Henzinger","year":"1996","unstructured":"M. Henzinger and J.A. Telle. Faster algorithms for the nonemptiness of Streett automata and for communication protocol pruning. In Proc. 5th Scandinavian Workshop on Algorithm Theory, volume 1097 of Lecture Notes in Computer Science, pages 10\u201320. Springer-Verlag, 1996."},{"issue":"3","key":"18_CR8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzinski","year":"1998","unstructured":"M. Jurdzinski. Deciding the winner in parity games is in up \u2229 co-up. Information Processing Letters, 68(3):119\u2013124, 1998.","journal-title":"Information Processing Letters"},{"key":"18_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1007\/3-540-60246-1_160","volume-title":"Proc. 20th International Symp. on Mathematical Foundations of Computer Science","author":"D. Janin","year":"1995","unstructured":"D. Janin and I. Walukiewicz. Automata for the modal \u03bc-calculus and related results. In Proc. 20th International Symp. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, pages 552\u2013562. Springer-Verlag, 1995."},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D. Kozen","year":"1983","unstructured":"D. Kozen. Results on the propositional \u03bc-calculus. Theoretical Computer Science, 27:333\u2013354, 1983.","journal-title":"Theoretical Computer Science"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"R.P. Kurshan. Computer Aided Verification of Coordinating Processes. Princeton Univ. Press, 1994.","DOI":"10.1515\/9781400864041"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R. McNaughton","year":"1966","unstructured":"R. McNaughton. Testing and generating infinite sequences by a finite automaton. Information and Control, 9:521\u2013530, 1966.","journal-title":"Information and Control"},{"key":"18_CR13","series-title":"Lect Notes Comput Sci","first-page":"157","volume-title":"Computation Theory","author":"A.W. Mostowski","year":"1984","unstructured":"A.W. Mostowski. Regular expressions for infinite trees and a standard form of automata. In Computation Theory, volume 208 of Lecture Notes in Computer Science, pages 157\u2013168. Springer-Verlag, 1984."},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"M.O. Rabin. Decidability of second order theories and automata on infinite trees. Transaction of the AMS, 141:1\u201335, 1969.","journal-title":"Transaction of the AMS"},{"issue":"4-5","key":"18_CR15","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1051\/ita:1999101","volume":"33","author":"H. Seidl","year":"1999","unstructured":"H. Seidl and D. Niwi\u0144ski. On distributive fixed-point expressions. Theoretical Informatics and Applications, 33(4-5):427\u2013446, 1999.","journal-title":"Theoretical Informatics and Applications"},{"issue":"2","key":"18_CR16","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"R.E. Tarjan. Depth first search and linear graph algorithms. SIAM Journal of Computing, 1(2):146\u2013160, 1972.","journal-title":"SIAM Journal of Computing"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/0020-0190(82)90136-3","volume":"14","author":"R.E. Tarjan","year":"1982","unstructured":"R.E. Tarjan. A hierarchical clustering algorithm using strong components. Information Processing Letters, 14:26\u201329, 1982.","journal-title":"Information Processing Letters"},{"key":"18_CR18","unstructured":"M.Y. Vardi and P. Wolper. An automata-theoretic approach to automatic program verification. In Proc. 1st Symp. on Logic in Computer Science, pages 332\u2013344, Cambridge, June 1986."},{"issue":"1","key":"18_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1994.1092","volume":"115","author":"M.Y. Vardi","year":"1994","unstructured":"M.Y. Vardi and P. Wolper. Reasoning about infinite computations. Information and Computation, 115(1):1\u201337, November 1994.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45315-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,5]],"date-time":"2019-05-05T09:10:04Z","timestamp":1557047404000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45315-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540418641","9783540453154"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45315-6_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}