{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:30:46Z","timestamp":1742913046627,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031199912"},{"type":"electronic","value":"9783031199929"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-19992-9_12","type":"book-chapter","created":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T09:12:06Z","timestamp":1666429926000},"page":"191-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimization of\u00a0Automata for\u00a0Liveness Languages"],"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":[]}],"member":"297","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"key":"12_CR1","unstructured":"Abu Radi, B., Kupferman, O.: Minimizing GFG transition-based automata. In: Proceedings of 46th International Colloquium on Automata, Languages, and Programming. LIPIcs, vol. 132, pp. 100:1\u2013100:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019)"},{"key":"12_CR2","unstructured":"Abu Radi, B., Kupferman, O., Leshkowitz, O.: A hierarchy of nondeterminism. In: 46th International Symposium on Mathematical Foundations of Computer Science. LIPIcs, vol. 202, pp. 85:1\u201385:21 (2021)"},{"key":"12_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":"12_CR4","unstructured":"Boker, U., Lehtinen, K.: Good for games automata: from nondeterminism to alternation. In: Proceedings of 30th International Conference on Concurrency Theory. LIPIcs, vol. 140, pp. 19:1\u201319:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"12_CR5","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":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-030-59152-6_9","volume-title":"Automated Technology for Verification and Analysis","author":"R Faran","year":"2020","unstructured":"Faran, R., Kupferman, O.: On (I\/O)-aware good-for-games automata. In: Hung, D.V., Sokolsky, O. (eds.) ATVA 2020. LNCS, vol. 12302, pp. 161\u2013178. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59152-6_9"},{"key":"12_CR7","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"},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-030-24886-4_14","volume-title":"Developments in Language Theory","author":"S Iosti","year":"2019","unstructured":"Iosti, S., Kuperberg, D.: Eventually safe languages. In: Hofman, P., Skrzypczak, M. (eds.) DLT 2019. LNCS, vol. 11647, pp. 192\u2013205. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-24886-4_14"},{"issue":"6","key":"12_CR9","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T Jiang","year":"1993","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput. 22(6), 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-662-47666-6_24","volume-title":"Automata, Languages, and Programming","author":"D Kuperberg","year":"2015","unstructured":"Kuperberg, D., Skrzypczak, M.: On determinisation of good-for-games automata. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 299\u2013310. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_24"},{"key":"12_CR11","unstructured":"Kupferman, O., Leshkowitz, O.: On repetition languages. In: 45th International Symposium on Mathematical Foundations of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs) (2020)"},{"issue":"1\u20133","key":"12_CR12","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.: Relating word and tree automata. Ann. Pure Appl. Logic 138(1\u20133), 126\u2013146 (2006)","journal-title":"Ann. Pure Appl. Logic"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/BF01691063","volume":"3","author":"L Landweber","year":"1969","unstructured":"Landweber, L.: Decision problems for $$\\omega $$-automata. Math. Syst. Theory 3, 376\u2013384 (1969)","journal-title":"Math. Syst. Theory"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"27081","DOI":"10.1109\/ACCESS.2017.2773123","volume":"5","author":"W Li","year":"2017","unstructured":"Li, W., Kan, S., Huang, Z.: A better translation from LTL to transition-based generalized B\u00fcchi automata. IEEE Access 5, 27081\u201327090 (2017)","journal-title":"IEEE Access"},{"issue":"3","key":"12_CR15","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0020-0190(00)00183-6","volume":"79","author":"C L\u00f6ding","year":"2001","unstructured":"L\u00f6ding, C.: Efficient minimization of deterministic weak $$\\omega $$-automata. Inf. Process. Lett. 79(3), 105\u2013109 (2001)","journal-title":"Inf. Process. Lett."},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Muller, D., Saoudi, A., Schupp, P.E.: Weak alternating automata give a simple explanation of why most temporal and dynamic logics are decidable in exponential time. In: Proceedings of 3rd IEEE Symposium on Logic in Computer Science, pp. 422\u2013427 (1988)","DOI":"10.1109\/LICS.1988.5139"},{"key":"12_CR17","unstructured":"Myhill, J.: Finite automata and the representation of events. Technical report WADD TR-57-624, pp. 112\u2013137. Wright Patterson AFB, Ohio (1957)"},{"issue":"4","key":"12_CR18","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformations. Proc. Am. Math. Soc. 9(4), 541\u2013544 (1958)","journal-title":"Proc. Am. Math. Soc."},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/BFb0028571","volume-title":"STACS 98","author":"D Niwi\u0144ski","year":"1998","unstructured":"Niwi\u0144ski, D., Walukiewicz, I.: Relating hierarchies of word and tree automata. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol. 1373, pp. 320\u2013331. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0028571"},{"key":"12_CR20","unstructured":"Schewe, S.: Beyond Hyper-Minimisation\u2013Minimising DBAs and DPAs is NP-complete. In: Proceedings of 30th Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), vol. 8, pp. 400\u2013411 (2010)"},{"key":"12_CR21","unstructured":"Schewe, S.: Minimising good-for-games automata is NP-complete. In: Proceedings of 40th Conference on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, vol. 182, pp. 56:1\u201356:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"}],"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-19992-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T10:00:56Z","timestamp":1728208856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-19992-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031199912","9783031199929"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-19992-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"21 October 2022","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":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"atva2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/atva-conference.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"81","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the COVID-19 pandemic, the conference was held virtually. Additional to the 26 papers, 1 invited talk is included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}