{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T14:50:12Z","timestamp":1791298212100,"version":"4.1.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T00:00:00Z","timestamp":1187049600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>In this paper we revisit Safra's determinization constructions for automata\non infinite words. We show how to construct deterministic automata with fewer\nstates and, most importantly, parity acceptance conditions. Determinization is\nused in numerous applications, such as reasoning about tree automata,\nsatisfiability of CTL*, and realizability and synthesis of logical\nspecifications. The upper bounds for all these applications are reduced by\nusing the smaller deterministic automata produced by our construction. In\naddition, the parity acceptance conditions allows to use more efficient\nalgorithms (when compared to handling Rabin or Streett acceptance conditions).<\/jats:p>","DOI":"10.2168\/lmcs-3(3:5)2007","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T13:10:09Z","timestamp":1212498609000},"source":"Crossref","is-referenced-by-count":99,"title":["From Nondeterministic B\\\"uchi and Streett Automata to Deterministic Parity Automata"],"prefix":"10.46298","volume":"Volume 3, Issue 3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8242-5357","authenticated-orcid":false,"given":"Nir","family":"Piterman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2007,8,14]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1199\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1199\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:05:43Z","timestamp":1681243543000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,14]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-3(3:5)2007","relation":{"is-same-as":[{"id-type":"arxiv","id":"0705.2205","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0705.2205","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8,14]]},"article-number":"1199"}}