{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:17:57Z","timestamp":1758273477251,"version":"3.41.2"},"reference-count":55,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T00:00:00Z","timestamp":1673568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Comput. Sci."],"abstract":"<jats:p>Nondeterminism models an ability to see the future: An automaton with an infinite look ahead can successfully resolve its nondeterministic choices. An automaton is<jats:italic>history deterministic<\/jats:italic>(HD) if it can successfully resolve its nondeterministic choices in a way that only depends on the past. Formally, an HD automaton has a strategy that maps each finite word to the transition to be taken after the word is read and following this strategy results in accepting all the words in the language of the automaton. Beyond being theoretically interesting and intriguing, HD automata can replace deterministic automata in several applications, most notably reactive synthesis, and they attract a lot of interest in the research community. The survey describes the development of HD \u03c9-regular automata, relates history determinism to other types of bounded nondeterminism, studies the determinization of HD automata and their succinctness with respect to deterministic ones, and discusses variants, extensions, and open problems around HD automata.<\/jats:p>","DOI":"10.3389\/fcomp.2022.1114625","type":"journal-article","created":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T05:29:12Z","timestamp":1673587752000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Using the past for resolving the future"],"prefix":"10.3389","volume":"4","author":[{"given":"Orna","family":"Kupferman","sequence":"first","affiliation":[]}],"member":"1965","published-online":{"date-parts":[[2023,1,13]]},"reference":[{"key":"B1","first-page":"1","article-title":"\u201cMinimizing GFG transition-based automata,\u201d","volume":"100","author":"Abu Radi","year":"2019","journal-title":"Proceedings of 46th International Colloquium on Automata, Languages, and Programming, volume 132 of LIPIcs"},{"key":"B2","article-title":"\u201cCanonicity in GFG and transition-based automata,\u201d","author":"Abu Radi","year":"2020","journal-title":"Proceedings of 11th International Symposium on Games, Automata, Logics and Formal Verification. Electronic Proceedings in Theoretical Computer Science"},{"key":"B3","first-page":"191","article-title":"\u201cMinimization of automata for liveness languages,\u201d","volume-title":"20th International Symposium on Automated Technology for Verification and Analysis, volume 13505 of Lecture Notes in Computer Science","author":"Abu Radi","year":"2022"},{"key":"B4","first-page":"1","article-title":"\u201cA hierarchy of nondeterminism,\u201d","volume":"85","author":"Abu Radi","year":"2021","journal-title":"46th International Symposium on Mathematical Foundations of Computer Science, volume 202 of LIPIcs"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721844","article-title":"Reasoning about online algorithms with weighted automata","author":"Aminof","year":"2010","journal-title":"ACM Trans. Algorith"},{"key":"B6","first-page":"213","article-title":"\u201cFormal analysis of online algorithms,\u201d","volume-title":"9th International Symposium on Automated Technology for Verification and Analysis, volume 6996 of Lecture Notes in Computer Science","author":"Aminof","year":"2011"},{"key":"B7","first-page":"1","article-title":"\u201cB\u00fcchi good-for-games automata are efficiently recognizable,\u201d","volume-title":"Proceedings of 38th Conferences on Foundations of Software Technology and Theoretical Computer Science, volume 122 of LIPIcs","author":"Bagnol","year":"2018"},{"key":"B8","first-page":"89","article-title":"\u201cNondeterminism in the presence of a diverse or unknown future,\u201d","author":"Boker","year":"2013","journal-title":"Proceedings of 40th International Colloquium on Automata, Languages, and Programming, volume 7966 of Lecture Notes in Computer Science"},{"key":"B9","first-page":"1","article-title":"\u201cOn the succinctness of alternating parity good-for-games automata,\u201d","volume-title":"Proceedings of 40th Confeneces on Foundations of Software Technology and Theoretical Computer Science, volume 182 of LIPIcs","author":"Boker","year":"2020"},{"key":"B10","first-page":"76","article-title":"\u201cAlternation removal in B\u00fcchi automata,\u201d","author":"Boker","year":"2010","journal-title":"Proceedings of 37th International Colloquium on Automata, Languages, and Programming, Vol. 6199"},{"key":"B11","first-page":"1","article-title":"\u201cHow deterministic are Good-For-Games automata?\u201d","volume":"18","author":"Boker","year":"2017","journal-title":"Proceedings of 37th Confenrence on Foundations of Software Technology and Theoretical Computer Science, volume 93 of Leibniz International Proceedings in Informatics (LIPIcs)"},{"key":"B12","first-page":"1","article-title":"\u201cGood for games automata: from nondeterminism to alternation,\u201d","volume-title":"Proceedings of 30th International Conference on Concurrency Theory, volume 140 of LIPIcs","author":"Boker","year":"2019"},{"key":"B13","first-page":"1","article-title":"\u201cHistory determinism vs. good for gameness in quantitative automata,\u201d","volume-title":"Proceedings of 41st Conference on Foundations of Software Technology and Theoretical Computer Science, volume 213 of LIPIcs","author":"Boker","year":"2021"},{"key":"B14","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/3584676.3584682","article-title":"When a little nondeterminism goes a long way: an introduction to history-determinism","volume":"10","author":"Boker","year":"2023","journal-title":"ACM SIGLOG News"},{"key":"B15","first-page":"1","article-title":"\u201cOn a decision method in restricted second order arithmetic,\u201d","volume-title":"Proceedings of International Congress on Logic, Method, and Philosophy of Science. 1960","author":"B\u00fcchi","year":"1962"},{"key":"B16","first-page":"1","article-title":"\u201cOn the minimisation of transition-based rabin automata and the chromatic memory requirements of muller conditions,\u201d","volume-title":"Proceedings of 30th Annual Conferences of the European Association for Computer Science Logic, volume 216 of LIPIcs","author":"Casares","year":"2022"},{"key":"B17","first-page":"1","article-title":"\u201cOn the size of good-for-games rabin automata and its link with the memory in muller games,\u201d","volume-title":"Proceeings of 49th International Colloquium on Automata, Languages, and Programming, volume 229 of LIPIcs","author":"Casares","year":"2022"},{"key":"B18","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Mach"},{"key":"B19","first-page":"139","article-title":"\u201cThe theory of stabilisation monoids and regular cost functions,\u201d","volume-title":"Proceedings of 36th International Colloquium on Automata, Languages, and Programming, volume 5556 of Lecture Notes in Computer Science","author":"Colcombet","year":"2009"},{"volume-title":"Fonctions r\u00e9guli\u00e8res de co\u00fbt","year":"2013","author":"Colcombet","key":"B20"},{"key":"B21","first-page":"384","article-title":"\u201cOne theorem to rule them all: a unified translation of LTL into \u03c9-automata,\u201d","volume-title":"Proceedings of 33rd IEEE Symposium on Logic in Computer Science","author":"Esparza","year":"2018"},{"key":"B22","first-page":"161","article-title":"\u201cOn (I\/O)-aware good-for-games automata,\u201d","volume-title":"18th International Symposium on Automated Technology for Verification and Analysis, volume 12302 of Lecture Notes in Computer Science","author":"Faran","year":"2020"},{"key":"B23","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36387-4","author":"Gr\u00e4del","year":"2002","journal-title":"Automata, Logics, and Infinite Games: A Guide to Current Research, volume 2500 of Lecture Notes in Computer Science"},{"key":"B24","first-page":"1","article-title":"\u201cA bit of nondeterminism makes pushdown automata expressive and succinct,\u201d","volume-title":"46th International Symposium on Mathematical Foundations of Computer Science, volume 202 of LIPIcs","author":"Guha","year":"2021"},{"key":"B25","first-page":"306","article-title":"\u201cGood-for-MDPs automata for probabilistic analysis and reinforcement learning,\u201d","volume-title":"Proceedings of 26th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, volume 12078 of Lecture Notes in Computer Science","author":"Hahn","year":"2020"},{"key":"B26","first-page":"394","article-title":"\u201cSolving games without determinization,\u201d","volume-title":"Proceedings of 15th Annual Conference of the European Association for Computer Science Logic, volume 4207 of Lecture Notes in Computer Science","author":"Henzinger","year":"2006"},{"key":"B27","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","article-title":"\u201cAn nlogn algorithm for minimizing the states in a finite automaton,\u201d","volume-title":"The Theory of Machines and Computations","author":"Hopcroft","year":"1971"},{"key":"B28","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","article-title":"Minimal NFA problems are hard","volume":"22","author":"Jiang","year":"1993","journal-title":"SIAM J. Comput"},{"key":"B29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1006\/inco.1997.2624","article-title":"Determinization and memoryless winning strategies","volume":"133","author":"Jutla","year":"1997","journal-title":"Inf. Comput"},{"key":"B30","first-page":"382","article-title":"\u201cProgress measures, immediate determinacy, and a subset construction for tree automata,\u201d","volume-title":"Proceedings of 7th IEEE Symposium on Logic in Computer Science","author":"Klarlund","year":"1992"},{"key":"B31","first-page":"1","article-title":"\u201cWidth of non-deterministic automata,\u201d","volume-title":"Proceedings of 35th Symposium on Theoretical Aspects of Computer Science, volume 96 of LIPIcs","author":"Kuperberg","year":"2018"},{"key":"B32","first-page":"299","article-title":"\u201cOn determinisation of good-for-games automata,\u201d","author":"Kuperberg","year":"2015","journal-title":"Proceedings of 42nd International Colloquium on Automata, Languages, and Programming"},{"key":"B33","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-3-319-10575-8_4","article-title":"\u201cAutomata theory and model checking,\u201d","volume-title":"Handbook of Model Checking","author":"Kupferman","year":"2018"},{"key":"B34","first-page":"322","article-title":"\u201cRelating word and tree automata,\u201d","author":"Kupferman","year":"1996","journal-title":"Proceedings of 11th IEEE Symposium on Logic in Computer Science"},{"key":"B35","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.apal.2005.06.009","article-title":"Relating word and tree automata","volume":"138","author":"Kupferman","year":"2006","journal-title":"Ann. Pure Appl. Logic"},{"key":"B36","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/978-3-030-71995-1_20","article-title":"\u201cCertifying inexpressibility,\u201d","volume-title":"Proceedings of 24th International Conference on Foundations of Software Science and Computation Structures, volume 12650 of Lecture Notes in Computer Science","author":"Kupferman","year":"2021"},{"key":"B37","first-page":"531","article-title":"\u201cSafraless decision procedures,\u201d","volume-title":"Proceedings of 46th IEEE Symposium on Foundations of Computer Science","author":"Kupferman","year":"2005"},{"key":"B38","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/BF01691063","article-title":"Decision problems for \u03c9-automata","volume":"3","author":"Landweber","year":"1969","journal-title":"Math. Syst. Theory"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(1:3)2022","article-title":"Good-for-games \u03c9-pushdown automata","author":"Lehtinen","year":"2022","journal-title":"Logical Methods Comput. Sci"},{"key":"B40","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0304-3975(84)90049-5","article-title":"Alternating finite automata on \u03c9-words","volume":"32","author":"Miyano","year":"1984","journal-title":"Theor Comput. Sci"},{"volume-title":"Expressiveness results at the bottom of the","year":"2003","author":"Morgenstern","key":"B41"},{"journal-title":"Finite automata and the representation of events","year":"1957","author":"Myhill","key":"B42"},{"key":"B43","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","article-title":"Linear automaton transformations","volume":"9","author":"Nerode","year":"1958","journal-title":"Proc. Am. Math. Soc"},{"key":"B44","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0028571","article-title":"\u201cRelating hierarchies of word and tree automata,\u201d","volume-title":"Proceedings of 15th Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science","author":"Niwinski","year":"1998"},{"key":"B45","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0304-3975(81)90110-9","article-title":"The temporal semantics of concurrent programs","volume":"13","author":"Pnueli","year":"1981","journal-title":"Theor. Comput. Sci"},{"key":"B46","first-page":"179","article-title":"\u201cOn the synthesis of a reactive module,\u201d","author":"Pnueli","year":"1989","journal-title":"Proceedings of 16th ACM Symposium on Principles of Programming Languages"},{"key":"B47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0002-9947-1969-0246760-1","article-title":"Decidability of second order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Trans. AMS"},{"key":"B48","first-page":"1","article-title":"\u201cWeakly definable relations and special automata,\u201d","volume-title":"Proceedings of Symposium Mathematical Logic and Foundations of Set Theory","author":"Rabin","year":"1970"},{"key":"B49","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1147\/rd.32.0114","article-title":"Finite automata and their decision problems","volume":"3","author":"Rabin","year":"1959","journal-title":"IBM J. Res. Dev"},{"key":"B50","first-page":"319","article-title":"\u201cOn the complexity of \u03c9-automata,\u201d","volume-title":"Proceedings of 29th IEEE Symposium on Foundations of Computer Science","author":"Safra","year":"1988"},{"key":"B51","first-page":"400","article-title":"\u201cBeyond hyper-minimisation\u2013minimising DBAs and DPAs is NP-Complete,\u201d","author":"Schewe","year":"2010","journal-title":"Proceedings of 30th Conference on Foundations of Software Technology and Theoretical Computer Science, volume 8 of Leibniz International Proceedings in Informatics (LIPIcs)"},{"key":"B52","first-page":"1","article-title":"\u201cMinimising good-for-games automata is NP-complete,\u201d","volume-title":"Proceedings of 40th Conference on Foundations of Software Technology and Theoretical Computer Science, volume 182 of LIPIcs","author":"Schewe","year":"2020"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2202.07629","article-title":"Deciding what is good-for-MDPs","author":"Schewe","year":"2022","journal-title":"CoRR"},{"key":"B54","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/BF01211865","article-title":"Safety, liveness and fairness in temporal logic","volume":"6","author":"Sistla","year":"1994","journal-title":"Formal Aspects Comput"},{"key":"B55","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1994.1092","article-title":"Reasoning about infinite computations","volume":"115","author":"Vardi","year":"1994","journal-title":"Inf. Comput"}],"container-title":["Frontiers in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fcomp.2022.1114625\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T23:31:32Z","timestamp":1679355092000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fcomp.2022.1114625\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,13]]},"references-count":55,"alternative-id":["10.3389\/fcomp.2022.1114625"],"URL":"https:\/\/doi.org\/10.3389\/fcomp.2022.1114625","relation":{},"ISSN":["2624-9898"],"issn-type":[{"type":"electronic","value":"2624-9898"}],"subject":[],"published":{"date-parts":[[2023,1,13]]},"article-number":"1114625"}}