{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:19Z","timestamp":1750220179794,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft (DFG, German Research Foundation)","award":["grant 44846804"],"award-info":[{"award-number":["grant 44846804"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533371","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Regular Languages of First-Order Logic with One Alternation"],"prefix":"10.1145","author":[{"given":"Corentin","family":"Barloy","sequence":"first","affiliation":[{"name":"Universite de Lille, France"}]},{"given":"Michael","family":"Cadilhac","sequence":"additional","affiliation":[{"name":"DePaul University, USA"}]},{"given":"Charles","family":"Paperman","sequence":"additional","affiliation":[{"name":"Universite de Lille, France"}]},{"given":"Thomas","family":"Zeume","sequence":"additional","affiliation":[{"name":"Ruhr-Universitaet Bochum, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819679600009X"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90014-A"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.07.004"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63138"},{"key":"e_1_3_2_1_6_1","volume-title":"13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings(Lecture Notes in Computer Science, Vol.\u00a05583)","author":"Bojanczyk Mikolaj","year":"2009","unstructured":"Mikolaj Bojanczyk . 2009 . Factorization Forests. In Developments in Language Theory , 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings(Lecture Notes in Computer Science, Vol.\u00a05583) , Volker Diekert and Dirk Nowotka (Eds.). Springer, 1\u201317. https:\/\/doi.org\/10.1007\/978-3-642-02737-6_1 10.1007\/978-3-642-02737-6_1 Mikolaj Bojanczyk. 2009. Factorization Forests. In Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings(Lecture Notes in Computer Science, Vol.\u00a05583), Volker Diekert and Dirk Nowotka (Eds.). Springer, 1\u201317. https:\/\/doi.org\/10.1007\/978-3-642-02737-6_1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90049-1"},{"key":"e_1_3_2_1_8_1","volume-title":"The Regular Languages of Wire Linear AC0. (Dec","author":"Cadilhac Micha\u00ebl","year":"2021","unstructured":"Micha\u00ebl Cadilhac and Charles Paperman . 2021. The Regular Languages of Wire Linear AC0. (Dec . 2021 ). https:\/\/hal.archives-ouvertes.fr\/hal-03466451 Submitted to Acta Informatica, special issue for the 70th birthday of Klaus-J\u00f6rn Lange . Micha\u00ebl Cadilhac and Charles Paperman. 2021. The Regular Languages of Wire Linear AC0. (Dec. 2021). https:\/\/hal.archives-ouvertes.fr\/hal-03466451 Submitted to Acta Informatica, special issue for the 70th birthday of Klaus-J\u00f6rn Lange."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795282432"},{"key":"e_1_3_2_1_10_1","volume-title":"International Conference on Algorithmic Learning Theory, ALT 2017","author":"Ding Ning","year":"2017","unstructured":"Ning Ding , Yanli Ren , and Dawu Gu . 2017 . PAC Learning Depth-3 AC0 Circuits of Bounded Top Fanin . In International Conference on Algorithmic Learning Theory, ALT 2017 , 15-17 October 2017, Kyoto University, Kyoto, Japan(Proceedings of Machine Learning Research, Vol.\u00a076), Steve Hanneke and Lev Reyzin (Eds.). PMLR, 667\u2013680. http:\/\/proceedings.mlr.press\/v76\/ding17a.html Ning Ding, Yanli Ren, and Dawu Gu. 2017. PAC Learning Depth-3 AC0 Circuits of Bounded Top Fanin. In International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan(Proceedings of Machine Learning Research, Vol.\u00a076), Steve Hanneke and Lev Reyzin (Eds.). PMLR, 667\u2013680. http:\/\/proceedings.mlr.press\/v76\/ding17a.html"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646517.696337"},{"key":"e_1_3_2_1_13_1","volume-title":"42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017","author":"Grosshans Nathan","year":"2017","unstructured":"Nathan Grosshans , Pierre McKenzie , and Luc Segoufin . 2017 . The Power of Programs over Monoids in DA . In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 , August 21-25, 2017 - Aalborg, Denmark(LIPIcs, Vol.\u00a083), Kim\u00a0G. Larsen, Hans\u00a0L. Bodlaender, and Jean-Fran\u00e7ois Raskin (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2:1\u20132:20. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS. 2017.2 10.4230\/LIPIcs.MFCS.2017.2 Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. 2017. The Power of Programs over Monoids in DA. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark(LIPIcs, Vol.\u00a083), Kim\u00a0G. Larsen, Hans\u00a0L. Bodlaender, and Jean-Fran\u00e7ois Raskin (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2:1\u20132:20. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2017.2"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90001-D"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01268140"},{"key":"e_1_3_2_1_16_1","first-page":"143","article-title":"Almost Optimal Lower Bounds for Small Depth","volume":"5","author":"H\u00e5stad John","year":"1989","unstructured":"John H\u00e5stad . 1989 . Almost Optimal Lower Bounds for Small Depth Circuits. Adv. Comput. Res. 5 (1989), 143 \u2013 170 . John H\u00e5stad. 1989. Almost Optimal Lower Bounds for Small Depth Circuits. Adv. Comput. Res. 5(1989), 143\u2013170.","journal-title":"Circuits. Adv. Comput. Res."},{"volume-title":"Extremal Combinatorics - With Applications in Computer Science","author":"Jukna Stasys","key":"e_1_3_2_1_17_1","unstructured":"Stasys Jukna . 2011. Extremal Combinatorics - With Applications in Computer Science ( second ed.). Springer . https:\/\/doi.org\/10.1007\/978-3-642-17364-6 10.1007\/978-3-642-17364-6 Stasys Jukna. 2011. Extremal Combinatorics - With Applications in Computer Science (second ed.). Springer. https:\/\/doi.org\/10.1007\/978-3-642-17364-6"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9180-z"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060629"},{"volume-title":"Combinatorics on words","author":"Lothaire M.","key":"e_1_3_2_1_20_1","unstructured":"M. Lothaire . 1997. Combinatorics on words ( second ed.). Cambridge University Press . M. Lothaire. 1997. Combinatorics on words(second ed.). Cambridge University Press."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00278-9"},{"volume-title":"The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, Stavros Konstantinidis, Nelma Moreira, Rog\u00e9rio Reis, and Jeffrey\u00a0O","author":"Pin Jean-\u00c9ric","key":"e_1_3_2_1_22_1","unstructured":"Jean-\u00c9ric Pin . 2017. The Dot-Depth Hierarchy, 45 Years Later . In The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, Stavros Konstantinidis, Nelma Moreira, Rog\u00e9rio Reis, and Jeffrey\u00a0O . Shallit (Eds.). World Scientific , 177\u2013202. https:\/\/doi.org\/10.1142\/9789813148208_0008 10.1142\/9789813148208_0008 Jean-\u00c9ric Pin. 2017. The Dot-Depth Hierarchy, 45 Years Later. In The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, Stavros Konstantinidis, Nelma Moreira, Rog\u00e9rio Reis, and Jeffrey\u00a0O. Shallit (Eds.). World Scientific, 177\u2013202. https:\/\/doi.org\/10.1142\/9789813148208_0008"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679467"},{"key":"e_1_3_2_1_24_1","volume-title":"A variety theorem without complementation. Russian Mathematics (Izvestija vuzov. Matematika) 39","author":"Pin Jean-\u00c9ric","year":"1995","unstructured":"Jean-\u00c9ric Pin . 1995. A variety theorem without complementation. Russian Mathematics (Izvestija vuzov. Matematika) 39 ( 1995 ), 80\u201390. Jean-\u00c9ric Pin. 1995. A variety theorem without complementation. Russian Mathematics (Izvestija vuzov. Matematika) 39 (1995), 80\u201390."},{"key":"e_1_3_2_1_25_1","volume-title":"Separating regular languages with two quantifier alternations. Log. Methods Comput. Sci. 14, 4","author":"Place Thomas","year":"2018","unstructured":"Thomas Place . 2018. Separating regular languages with two quantifier alternations. Log. Methods Comput. Sci. 14, 4 ( 2018 ). https:\/\/doi.org\/10.23638\/LMCS-14(4:16)2018 10.23638\/LMCS-14(4:16)2018 Thomas Place. 2018. Separating regular languages with two quantifier alternations. Log. Methods Comput. Sci. 14, 4 (2018). https:\/\/doi.org\/10.23638\/LMCS-14(4:16)2018"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3303991"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808733"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030341"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(85)90062-3"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196791000043"},{"volume-title":"Formal Logic, and Circuit Complexity","author":"Straubing Howard","key":"e_1_3_2_1_31_1","unstructured":"Howard Straubing . 1994. Finite Automata , Formal Logic, and Circuit Complexity . Birkh\u00e4user , Boston . https:\/\/doi.org\/10.1007\/978-1-4612-0289-9 10.1007\/978-1-4612-0289-9 Howard Straubing. 1994. Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston. https:\/\/doi.org\/10.1007\/978-1-4612-0289-9"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2923"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196715400111"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276749"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(87)90108-3"}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"],"location":"Haifa Israel","acronym":"LICS '22"},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533371","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":35,"alternative-id":["10.1145\/3531130.3533371","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533371","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}