{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:19:36Z","timestamp":1760080776870,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p>History-deterministic automata are an intermediate automata model, in between deterministic and nondeterministic ones. An automaton is history-deterministic if its nondeterminism can be resolved on-the-fly, by only taking into account the prefix of the word read so far. This restricted form of nondeterminism yields a class of automata that retains some of the algorithmic properties of deterministic automata, while also enjoying some of the power of nondeterminism.<\/jats:p>\n          <jats:p>History-determinism has received a lot of attention in the past few years and this article surveys some of the recent developments on the topic. It aims to showcase some of the key constructions and techniques involved in this line of research, while remaining fairly informal.<\/jats:p>\n          <jats:p>We begin with a roughly chronological overview of research on history-determinism, intended as a quick reference to some of the main results on the subject. We then move onto a more detailed discussion of what are, in our view, the key aspects of history-determinism, highlighting throughout questions that remain open. Like any survey written on a topic that is actively worked on, this article aspires to be out-of-date as soon as it is published. We hope that it will remain useful as a gentle, if incomplete, introduction to the topic.<\/jats:p>","DOI":"10.1145\/3584676.3584682","type":"journal-article","created":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T17:31:02Z","timestamp":1676395862000},"page":"24-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["When a Little Nondeterminism Goes a Long Way"],"prefix":"10.1145","volume":"10","author":[{"given":"Udi","family":"Boker","sequence":"first","affiliation":[{"name":"Reichman University, Herzliya, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karoliina","family":"Lehtinen","sequence":"additional","affiliation":[{"name":"Aix-Marseille Universit\u00e9, Marseille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(3:16)2022"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53291-8-28"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721844"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2018.16"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4\\_14"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.29007\/c3bj"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-89716-1_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2022.1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_11"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2002.07278"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2020.41"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2017.18"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2019.19"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2021.38"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Udi Boker and Karoliina Lehtinen. 2022. Token Games and History-Deterministic Quantitative Automata. In FOSSACS. 120--139. A submitted journal version is available at https:\/\/arxiv.org\/abs\/2110.14308.  Udi Boker and Karoliina Lehtinen. 2022. Token Games and History-Deterministic Quantitative Automata. In FOSSACS. 120--139. A submitted journal version is available at https:\/\/arxiv.org\/abs\/2110.14308.","DOI":"10.1007\/978-3-030-99253-8_7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-19135-0\\_5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1145288"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2022.12"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.117"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805950.1805953"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2271310"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_12"},{"key":"e_1_2_1_23_1","volume-title":"Fonctions r\u00e9guli\u00e8res de co\u00fbt. Habilitation \u00e0 diriger les recherches, \u00c9cole Doctorale de Sciences Math\u00e9matiques de Paris Centre","author":"Colcombet Thomas","year":"2013","unstructured":"Thomas Colcombet . 2013. Fonctions r\u00e9guli\u00e8res de co\u00fbt. Habilitation \u00e0 diriger les recherches, \u00c9cole Doctorale de Sciences Math\u00e9matiques de Paris Centre ( 2013 ). \\url{https:\/\/www.irif.fr\/~colcombe\/Publications\/habilitation-colcombet_v1.1.pdf} Thomas Colcombet. 2013. Fonctions r\u00e9guli\u00e8res de co\u00fbt. Habilitation \u00e0 diriger les recherches, \u00c9cole Doctorale de Sciences Math\u00e9matiques de Paris Centre (2013). \\url{https:\/\/www.irif.fr\/~colcombe\/Publications\/habilitation-colcombet_v1.1.pdf}"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.126"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3\\_33"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.36"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2209.07745"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005096"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2020.46"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2021.53"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2105.02611"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209010"},{"key":"e_1_2_1_33_1","volume-title":"Proc. of CSL.","author":"Hazard \u00c9mile","year":"2023","unstructured":"\u00c9mile Hazard and Denis Kuperberg . 2023 . Explorable automata . In Proc. of CSL. \u00c9mile Hazard and Denis Kuperberg. 2023. Explorable automata. In Proc. of CSL."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_26"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3085"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2022.14"},{"key":"e_1_2_1_37_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"2007","unstructured":"John E. Hopcroft , Rajeev Motwani , and Jeffrey D . Ullman . 2007 . Introduction to automata theory, languages, and computation, 3 rd Edition. Addison-Wesley . John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2007. Introduction to automata theory, languages, and computation, 3rd Edition. Addison-Wesley.","edition":"3"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2016.30"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-016-0268-z"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24886-4\\_14"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_24"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Orna Kupferman. 2023. Using the Past for Resolving the Future. (2023). To appear.  Orna Kupferman. 2023. Using the Past for Resolving the Future. (2023). To appear.","DOI":"10.3389\/fcomp.2022.1114625"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.06.009"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(1:3)2022"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2013.327"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2210.10084"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73019"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2020.56"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(76)90173-X"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584676.3584682","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584676.3584682","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:59Z","timestamp":1750268999000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584676.3584682"}},"subtitle":["An Introduction to History-Determinism"],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.1145\/3584676.3584682"],"URL":"https:\/\/doi.org\/10.1145\/3584676.3584682","relation":{},"ISSN":["2372-3491"],"issn-type":[{"type":"electronic","value":"2372-3491"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"2023-02-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}