{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T06:07:53Z","timestamp":1776233273598,"version":"3.50.1"},"reference-count":121,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100005304","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0007"],"award-info":[{"award-number":["ANR-16-CE40-0007"]}],"id":[{"id":"10.13039\/501100005304","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            We investigate quantifier alternation hierarchies in first-order logic on finite words. Levels in these hierarchies are defined by counting the number of quantifier alternations in formulas. We prove that one can decide membership of a regular language in the levels B\u03a3\n            <jats:sub>2<\/jats:sub>\n            (finite Boolean combinations of formulas having only one alternation) and \u03a3\n            <jats:sub>3<\/jats:sub>\n            (formulas having only two alternations and beginning with an existential block). Our proofs work by considering a deeper problem, called\n            <jats:italic>separation<\/jats:italic>\n            , which, once solved for lower levels, allows us to solve membership for higher\u00a0levels.\n          <\/jats:p>","DOI":"10.1145\/3303991","type":"journal-article","created":{"date-parts":[[2019,3,14]],"date-time":"2019-03-14T17:11:58Z","timestamp":1552583518000},"page":"1-65","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Going Higher in First-Order Quantifier Alternation Hierarchies on Words"],"prefix":"10.1145","volume":"66","author":[{"given":"Thomas","family":"Place","sequence":"first","affiliation":[{"name":"LaBRI, Bordeaux University and Institut Universitaire de France, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Zeitoun","sequence":"additional","affiliation":[{"name":"LaBRI, Bordeaux University, Talence Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275184"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(91)90019-X"},{"key":"e_1_2_1_3_1","volume-title":"Finite Semigroups and Universal Algebra. World Scientific","author":"Almeida Jorge","unstructured":"Jorge Almeida . 1995. Finite Semigroups and Universal Algebra. World Scientific , Singapore . Jorge Almeida. 1995. Finite Semigroups and Universal Algebra. World Scientific, Singapore."},{"key":"e_1_2_1_4_1","first-page":"531","article-title":"Some algorithmic problems for pseudovarieties","volume":"54","author":"Almeida Jorge","year":"1999","unstructured":"Jorge Almeida . 1999 . Some algorithmic problems for pseudovarieties . Publicationes Mathematicae Debrecen 54 (1999), 531 -- 552 . Jorge Almeida. 1999. Some algorithmic problems for pseudovarieties. Publicationes Mathematicae Debrecen 54 (1999), 531--552.","journal-title":"Publicationes Mathematicae Debrecen"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.09.011"},{"key":"e_1_2_1_6_1","volume-title":"New decidable upper bound of the 2nd level in the Straubing-Th\u00e9rien concatenation hierarchy of star-free languages. Discrete Mathematics 8 Theoretical Computer Science 12, 4","author":"Almeida Jorge","year":"2010","unstructured":"Jorge Almeida and Ondrej Kl\u00edma . 2010. New decidable upper bound of the 2nd level in the Straubing-Th\u00e9rien concatenation hierarchy of star-free languages. Discrete Mathematics 8 Theoretical Computer Science 12, 4 ( 2010 ), 41--58. Jorge Almeida and Ondrej Kl\u00edma. 2010. New decidable upper bound of the 2nd level in the Straubing-Th\u00e9rien concatenation hierarchy of star-free languages. Discrete Mathematics 8 Theoretical Computer Science 12, 4 (2010), 41--58."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1997310504571"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/646503.696263"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90268-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196710005571"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01194543"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646243.681598"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90258-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.05.015"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02737-6_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_13"},{"key":"e_1_2_1_17_1","first-page":"33","article-title":"Hierarchies of aperiodic languages","volume":"10","author":"Brzozowski Janusz A.","year":"1976","unstructured":"Janusz A. Brzozowski . 1976 . Hierarchies of aperiodic languages . ITA 10 , 2 (1976), 33 -- 49 . Janusz A. Brzozowski. 1976. Hierarchies of aperiodic languages. ITA 10, 2 (1976), 33--49.","journal-title":"ITA"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(71)80003-X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90049-1"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 12th Annual Symposium on Switching and Automata Theory (SWAT\u201971)","author":"Janusz","unstructured":"Janusz A. Brzozowski and Imre Simon. 1971. Characterizations of locally testable events . In Proceedings of the 12th Annual Symposium on Switching and Automata Theory (SWAT\u201971) . IEEE, East Lansing, MI, 166--176. Janusz A. Brzozowski and Imre Simon. 1971. Characterizations of locally testable events. In Proceedings of the 12th Annual Symposium on Switching and Automata Theory (SWAT\u201971). IEEE, East Lansing, MI, 166--176."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(73)80005-6"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90075-D"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.10.013"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022896.2022898"},{"key":"e_1_2_1_26_1","series-title":"Handbook of Automata Theory, Jean-\u00c9ric Pin (Ed.).","volume-title":"Theoretical Foundations. Eur. Math. Soc., Z\u00fcrich. To appear.","author":"Colcombet Thomas","unstructured":"Thomas Colcombet . 2019. The factorisation forest theorem . In Handbook of Automata Theory, Jean-\u00c9ric Pin (Ed.). Vol. I : Theoretical Foundations. Eur. Math. Soc., Z\u00fcrich. To appear. Thomas Colcombet. 2019. The factorisation forest theorem. In Handbook of Automata Theory, Jean-\u00c9ric Pin (Ed.). Vol. I: Theoretical Foundations. Eur. Math. Soc., Z\u00fcrich. To appear."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196793000263"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_16"},{"key":"e_1_2_1_29_1","volume-title":"Logic and Automata: History and Perspectives, J\u00f6rg Flum, Erich Gr\u00e4del, and Thomas Wilke (Eds.). Texts in Logic and Games","author":"Diekert Volker","unstructured":"Volker Diekert and Paul Gastin . 2008. First-order definable languages . In Logic and Automata: History and Perspectives, J\u00f6rg Flum, Erich Gr\u00e4del, and Thomas Wilke (Eds.). Texts in Logic and Games , Vol. 2 . Amsterdam University Press , Amsterdam , the Netherlands, 261--306. Volker Diekert and Paul Gastin. 2008. First-order definable languages. In Logic and Automata: History and Perspectives, J\u00f6rg Flum, Erich Gr\u00e4del, and Thomas Wilke (Eds.). Texts in Logic and Games, Vol. 2. Amsterdam University Press, Amsterdam, the Netherlands, 261--306."},{"key":"e_1_2_1_30_1","unstructured":"Samuel Eilenberg. 1976. Automata Languages and Machines. Vol. B. Academic Press Orlando FL.   Samuel Eilenberg. 1976. Automata Languages and Machines. Vol. B. Academic Press Orlando FL."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201900)","volume":"1770","author":"Gla\u00dfer Christian","year":"2000","unstructured":"Christian Gla\u00dfer and Heinz Schmitz . 2000 . Languages of dot-depth 3\/2 . In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201900) , Lecture Notes in Computer Science, Horst Reichel and Sophie Tison (Eds.) , Vol. 1770 . Springer, Berlin, 555--566. Christian Gla\u00dfer and Heinz Schmitz. 2000. Languages of dot-depth 3\/2. In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201900), Lecture Notes in Computer Science, Horst Reichel and Sophie Tison (Eds.), Vol. 1770. Springer, Berlin, 555--566."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9002-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90031-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(88)90042-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1388-8_6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196710005662"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00230-7"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196700000066"},{"key":"e_1_2_1_40_1","volume-title":"Automata and Languages","author":"Howie John M.","unstructured":"John M. Howie . 1991. Automata and Languages . Clarendon Press , Oxford . John M. Howie. 1991. Automata and Languages. Clarendon Press, Oxford."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Neil Immerman. 1999. Descriptive Complexity. Springer Berlin.  Neil Immerman. 1999. Descriptive Complexity. Springer Berlin.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.11.008"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.06.013"},{"key":"e_1_2_1_44_1","volume-title":"Developments in Language Theory","author":"Kl\u00edma Ond\u0159ej","unstructured":"Ond\u0159ej Kl\u00edma and Libor Pol\u00e1k . 2013. Alternative automata characterization of piecewise testable languages . In Developments in Language Theory . Springer , Berlin , 289--300. Ond\u0159ej Kl\u00edma and Libor Pol\u00e1k. 2013. Alternative automata characterization of piecewise testable languages. In Developments in Language Theory. Springer, Berlin, 289--300."},{"key":"e_1_2_1_45_1","volume-title":"A semigroup characterization of dot-depth one languages. RAIRO \u2014 Theoretical Informatics and Applications 17, 4","author":"Knast Robert","year":"1983","unstructured":"Robert Knast . 1983. A semigroup characterization of dot-depth one languages. RAIRO \u2014 Theoretical Informatics and Applications 17, 4 ( 1983 ), 321--330. Robert Knast. 1983. A semigroup characterization of dot-depth one languages. RAIRO \u2014 Theoretical Informatics and Applications 17, 4 (1983), 321--330."},{"key":"e_1_2_1_46_1","volume-title":"Some theorems on graph congruences. RAIRO \u2014Theoretical Informatics and Applications 17, 4","author":"Knast Robert","year":"1983","unstructured":"Robert Knast . 1983. Some theorems on graph congruences. RAIRO \u2014Theoretical Informatics and Applications 17, 4 ( 1983 ), 331--342. Robert Knast. 1983. Some theorems on graph congruences. RAIRO \u2014Theoretical Informatics and Applications 17, 4 (1983), 331--342."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85238-4_36"},{"key":"e_1_2_1_48_1","volume-title":"Semigroups and Combinatorial Applications","author":"Lallement G\u00e9rard","unstructured":"G\u00e9rard Lallement . 1979. Semigroups and Combinatorial Applications . John Wiley 8 Sons, New York, NY. G\u00e9rard Lallement. 1979. Semigroups and Combinatorial Applications. John Wiley 8 Sons, New York, NY."},{"key":"e_1_2_1_49_1","volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","unstructured":"Leonid Libkin . 2004. Elements of Finite Model Theory . Springer , Berlin . Leonid Libkin. 2004. Elements of Finite Model Theory. Springer, Berlin."},{"key":"e_1_2_1_50_1","volume-title":"S\u00e3o Paulo. Retrieved","author":"Lucchesi Cl\u00e1udio L.","year":"1979","unstructured":"Cl\u00e1udio L. Lucchesi , Imre Simon , Istvan Simon , Janos Simon , and Tomasz Kowaltowski . 1979 . Aspectos Te\u00f3ricos da Computa\u00e7\u00e3o. IMPA , S\u00e3o Paulo. Retrieved February 16, 2019 from http:\/\/www.impa.br\/opencms\/pt\/biblioteca\/cbm\/11CBM\/11_CBM_77_04.pdf. Cl\u00e1udio L. Lucchesi, Imre Simon, Istvan Simon, Janos Simon, and Tomasz Kowaltowski. 1979. Aspectos Te\u00f3ricos da Computa\u00e7\u00e3o. IMPA, S\u00e3o Paulo. Retrieved February 16, 2019 from http:\/\/www.impa.br\/opencms\/pt\/biblioteca\/cbm\/11CBM\/11_CBM_77_04.pdf."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573319"},{"key":"e_1_2_1_52_1","series-title":"Lecture Notes in Computer Science","volume-title":"Margolis and Jean-\u00c9ric Pin","author":"Stuart","year":"1985","unstructured":"Stuart W. Margolis and Jean-\u00c9ric Pin . 1985 . Products of group languages. In Proceedings of the 5th International Symposium on Fundamentals of Computation Theory (FCT\u201985), Lecture Notes in Computer Science , Lothar Budach (Ed.), Vol. 199 . Springer , Berlin, 285--299. Stuart W. Margolis and Jean-\u00c9ric Pin. 1985. Products of group languages. In Proceedings of the 5th International Symposium on Fundamentals of Computation Theory (FCT\u201985), Lecture Notes in Computer Science, Lothar Budach (Ed.), Vol. 199. Springer, Berlin, 285--299."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01761708"},{"key":"e_1_2_1_54_1","volume-title":"Papert","author":"McNaughton Robert","year":"1971","unstructured":"Robert McNaughton and Seymour A . Papert . 1971 . Counter-Free Automata. MIT Press , Cambridge, MA. Robert McNaughton and Seymour A. Papert. 1971. Counter-Free Automata. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/321510.321513"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1958-0135681-9"},{"key":"e_1_2_1_57_1","volume-title":"Formal Models and Semantics","author":"Perrin Dominique","unstructured":"Dominique Perrin . 1990. Finite automata . In Formal Models and Semantics . Elsevier , Amsterdam , 1--57. Dominique Perrin. 1990. Finite automata. In Formal Models and Semantics. Elsevier, Amsterdam, 1--57."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90037-1"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/576708"},{"key":"e_1_2_1_60_1","volume-title":"Semigroups, Formal Languages and Groups","author":"Pin Jean-\u00c9ric","unstructured":"Jean-\u00c9ric Pin . 1995. Finite semigroups and recognizable languages: An introduction . In Semigroups, Formal Languages and Groups . Springer , Berlin , 1--32. Jean-\u00c9ric Pin. 1995. Finite semigroups and recognizable languages: An introduction. In Semigroups, Formal Languages and Groups. Springer, Berlin, 1--32."},{"key":"e_1_2_1_61_1","first-page":"74","article-title":"A variety theorem without complementation","volume":"39","author":"Pin Jean-\u00c9ric","year":"1995","unstructured":"Jean-\u00c9ric Pin . 1995 . A variety theorem without complementation . Russian Mathematics (Izvestiya Vuzov. Matematika) 39 (1995), 74 -- 83 . Jean-\u00c9ric Pin. 1995. A variety theorem without complementation. Russian Mathematics (Izvestiya Vuzov. Matematika) 39 (1995), 74--83.","journal-title":"Russian Mathematics (Izvestiya Vuzov. Matematika)"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/646250.685516"},{"key":"e_1_2_1_63_1","volume-title":"Handbook of Formal Languages","author":"Pin Jean-\u00c9ric","unstructured":"Jean-\u00c9ric Pin . 1997. Syntactic semigroups . In Handbook of Formal Languages . Springer , Berlin , 679--746. Jean-\u00c9ric Pin. 1997. Syntactic semigroups. In Handbook of Formal Languages. Springer, Berlin, 679--746."},{"key":"e_1_2_1_64_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP\u201998)","author":"Pin Jean-\u00c9ric","unstructured":"Jean-\u00c9ric Pin . 1998. Bridges for concatenation hierarchies . In Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP\u201998) , Lecture Notes in Computer Science , Kim Guldstrand Larsen, Sven Skyum, and Glynn Winskel (Eds.), Vol. 1443 . Springer , Berlin , 431--442. Jean-\u00c9ric Pin. 1998. Bridges for concatenation hierarchies. In Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP\u201998), Lecture Notes in Computer Science, Kim Guldstrand Larsen, Sven Skyum, and Glynn Winskel (Eds.), Vol. 1443. Springer, Berlin, 431--442."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2004.04.027"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022278.2022282"},{"key":"e_1_2_1_67_1","volume-title":"Developments in Language Theory","author":"Pin Jean-\u00c9ric","unstructured":"Jean-\u00c9ric Pin . 2013. An explicit formula for the intersection of two polynomials of regular languages . In Developments in Language Theory . Springer , Berlin , 31--45. Jean-\u00c9ric Pin. 2013. An explicit formula for the intersection of two polynomials of regular languages. In Developments in Language Theory. Springer, Berlin, 31--45."},{"key":"e_1_2_1_68_1","volume-title":"The Role of Theory in Computer Science, Essays Dedicated to Janusz Brzozowski, Stavros Konstantinidis, Nelma Moreira, Rog\u00e9rio Reis, and Jeffrey Shallit (Eds.). World Scientific","author":"Pin Jean-\u00c9ric","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 Shallit (Eds.). World Scientific , Singapore , 177--202. 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 Shallit (Eds.). World Scientific, Singapore, 177--202."},{"key":"e_1_2_1_69_1","unstructured":"Jean-\u00c9ric Pin. 2018. Mathematical Foundations of Automata Theory. (2018). https:\/\/www.irif.fr\/&sim;jep\/MPRI\/MPRI.html.  Jean-\u00c9ric Pin. 2018. Mathematical Foundations of Automata Theory. (2018). https:\/\/www.irif.fr\/&sim;jep\/MPRI\/MPRI.html."},{"key":"e_1_2_1_70_1","volume-title":"Colloquia Mathematica Societatis Janos Bolyal","author":"Pin Jean-\u00c9ric","unstructured":"Jean-\u00c9ric Pin and Howard Straubing . 1981. Monoids of upper triangular Boolean matrices . In Semigroups. Structure and Universal Algebraic Problems, S. Schwarz, G. Poll\u00e1k, and O. Steinfeld (Eds.). Colloquia Mathematica Societatis Janos Bolyal , Vol. 39 . North-Holland , Szeged, Hungary , 259--272. Jean-\u00c9ric Pin and Howard Straubing. 1981. Monoids of upper triangular Boolean matrices. In Semigroups. Structure and Universal Algebraic Problems, S. Schwarz, G. Poll\u00e1k, and O. Steinfeld (Eds.). Colloquia Mathematica Societatis Janos Bolyal, Vol. 39. North-Holland, Szeged, Hungary, 259--272."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/646249.685349"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1996.0192"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01243597"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2001134"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1081\/AGB-120016005"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679467"},{"key":"e_1_2_1_77_1","volume-title":"Theories of Computability","author":"Pippenger Nicholas","unstructured":"Nicholas Pippenger . 1997. Theories of Computability . Cambridge University Press , Cambridge, UK . Nicholas Pippenger. 1997. Theories of Computability. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.28"},{"key":"e_1_2_1_79_1","unstructured":"Thomas Place Lorijn van Rooijen and Marc Zeitoun. 2013. Separating regular languages by locally testable and locally threshold testable languages. In Proceedings of the 33rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913) Leibniz International Proceedings in Informatics Anil Seth and Nisheeth K. Vishnoi (Eds.) Vol. 24. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik Dagstuhl Germany 363--375.  Thomas Place Lorijn van Rooijen and Marc Zeitoun. 2013. Separating regular languages by locally testable and locally threshold testable languages. In Proceedings of the 33rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913) Leibniz International Proceedings in Informatics Anil Seth and Nisheeth K. Vishnoi (Eds.) Vol. 24. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik Dagstuhl Germany 363--375."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_64"},{"key":"e_1_2_1_81_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Place Thomas","unstructured":"Thomas Place and Marc Zeitoun . 2014. Going higher in the first-order quantifier alternation hierarchy on words . In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914) , Lecture Notes in Computer Science , Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Vol. 8572 . Springer , Berlin , 342--353. Thomas Place and Marc Zeitoun. 2014. Going higher in the first-order quantifier alternation hierarchy on words. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914), Lecture Notes in Computer Science, Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Vol. 8572. Springer, Berlin, 342--353."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603098"},{"key":"e_1_2_1_83_1","volume-title":"Proceedings of the 32nd Annual Conference on Theoretical Aspects of Computer Science (STACS\u201915), Leibniz International Proceedings in Informatics, Ernst W. Mayr and Nicolas Ollinger (Eds.)","volume":"30","author":"Place Thomas","year":"2015","unstructured":"Thomas Place and Marc Zeitoun . 2015 . Separation and the successor relation . In Proceedings of the 32nd Annual Conference on Theoretical Aspects of Computer Science (STACS\u201915), Leibniz International Proceedings in Informatics, Ernst W. Mayr and Nicolas Ollinger (Eds.) , Vol. 30 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 662--675. Thomas Place and Marc Zeitoun. 2015. Separation and the successor relation. In Proceedings of the 32nd Annual Conference on Theoretical Aspects of Computer Science (STACS\u201915), Leibniz International Proceedings in Informatics, Ernst W. Mayr and Nicolas Ollinger (Eds.), Vol. 30. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 662--675."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815493.2815495"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603098"},{"key":"e_1_2_1_86_1","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Logics, and Infinite Games: A Guide to Current Research {outcome of a Dagstuhl seminar","author":"Reinhardt Klaus","year":"2001","unstructured":"Klaus Reinhardt . 2002. The complexity of translating logic to finite automata . In Automata, Logics, and Infinite Games: A Guide to Current Research {outcome of a Dagstuhl seminar , February 2001 }, Lecture Notes in Computer Science , Erich Gr\u00e4del, Wolfgang Thomas , and Thomas Wilke (Eds.), Vol. 2500 . Springer , Berlin, 231--238. Klaus Reinhardt. 2002. The complexity of translating logic to finite automata. In Automata, Logics, and Infinite Games: A Guide to Current Research {outcome of a Dagstuhl seminar, February 2001}, Lecture Notes in Computer Science, Erich Gr\u00e4del, Wolfgang Thomas, and Thomas Wilke (Eds.), Vol. 2500. Springer, Berlin, 231--238."},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02483902"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196799000278"},{"key":"e_1_2_1_89_1","volume-title":"Combinatorics on Words, Lothaire","author":"Sakarovitch Jacques","unstructured":"Jacques Sakarovitch and Imre Simon . 1997. Subwords . In Combinatorics on Words, Lothaire . Cambridge University Press , Cambridge, UK . 105--144. Jacques Sakarovitch and Imre Simon. 1997. Subwords. In Combinatorics on Words, Lothaire. Cambridge University Press, Cambridge, UK. 105--144."},{"key":"e_1_2_1_90_1","unstructured":"Marcel Paul Sch\u00fctzenberger. 1955-1956. Une th\u00e9orie alg\u00e9brique du codage. S\u00e9minaire Dubreil. Alg\u00e8bre et Th\u00e9orie Des Nombres 9 (1955-1956) 1--24. http:\/\/eudml.org\/doc\/111094.  Marcel Paul Sch\u00fctzenberger. 1955-1956. Une th\u00e9orie alg\u00e9brique du codage. S\u00e9minaire Dubreil. Alg\u00e8bre et Th\u00e9orie Des Nombres 9 (1955-1956) 1--24. http:\/\/eudml.org\/doc\/111094."},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90108-7"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02194921"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.5555\/646589.697341"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90047-L"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002330010051"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90003-9"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80058-9"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90036-0"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(85)90062-3"},{"key":"e_1_2_1_103_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 13th International Colloquium on Automata, Languages, and Programming (ICALP\u201986)","author":"Straubing Howard","unstructured":"Howard Straubing . 1986. Semigroups and languages of dot-depth 2 . In Proceedings of the 13th International Colloquium on Automata, Languages, and Programming (ICALP\u201986) , Lecture Notes in Computer Science , Laurent Kott (Ed.), Vol. 226 . Springer , Berlin , 416--423. Howard Straubing. 1986. Semigroups and languages of dot-depth 2. In Proceedings of the 13th International Colloquium on Automata, Languages, and Programming (ICALP\u201986), Lecture Notes in Computer Science, Laurent Kott (Ed.), Vol. 226. Springer, Berlin, 416--423."},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90034-5"},{"key":"e_1_2_1_105_1","volume-title":"Finite Automata, Formal Logic and Circuit Complexity","author":"Straubing Howard","unstructured":"Howard Straubing . 1994. Finite Automata, Formal Logic and Circuit Complexity . Birkhauser , Basel, Switzerland . Howard Straubing. 1994. Finite Automata, Formal Logic and Circuit Complexity. Birkhauser, Basel, Switzerland."},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(88)90067-1"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90121-U"},{"key":"e_1_2_1_108_1","volume-title":"Diamonds are forever: The variety DA","author":"Tesson Pascal","unstructured":"Pascal Tesson and Denis Th\u00e9rien . 2002. Diamonds are forever: The variety DA . In Semigroups, Algorithms, Automata and Languages, Gracinda M. S. Gomes, Jean Eric Pin, and Pedro V. Silva (Eds.). World Scientific , Singapore , 475--500. Pascal Tesson and Denis Th\u00e9rien. 2002. Diamonds are forever: The variety DA. In Semigroups, Algorithms, Automata and Languages, Gracinda M. S. Gomes, Jean Eric Pin, and Pedro V. Silva (Eds.). World Scientific, Singapore, 475--500."},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90057-8"},{"key":"e_1_2_1_110_1","series-title":"Lecture Notes in Computer Science","volume-title":"Descriptional Complexity of Formal Systems","author":"Th\u00e9rien Denis","unstructured":"Denis Th\u00e9rien . 2011. The power of diversity . In Descriptional Complexity of Formal Systems , Lecture Notes in Computer Science , Markus Holzer, Martin Kutrib, and Giovanni Pighizzini (Eds.), Vol. 6808 . Springer , Berlin , 43--54. Denis Th\u00e9rien. 2011. The power of diversity. In Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science, Markus Holzer, Martin Kutrib, and Giovanni Pighizzini (Eds.), Vol. 6808. Springer, Berlin, 43--54."},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(85)90071-4"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276749"},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90016-2"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.24033\/msmf.309"},{"key":"e_1_2_1_115_1","volume-title":"Computation Theory and Logic","author":"Thomas Wolfgang","unstructured":"Wolfgang Thomas . 1987. A concatenation game and the dot-depth hierarchy . In Computation Theory and Logic . Springer , Berlin , 415--426. Wolfgang Thomas. 1987. A concatenation game and the dot-depth hierarchy. In Computation Theory and Logic. Springer, Berlin, 415--426."},{"key":"e_1_2_1_116_1","volume-title":"Handbook of Formal Languages","author":"Thomas Wolfgang","unstructured":"Wolfgang Thomas . 1997. Languages , automata, and logic . In Handbook of Formal Languages . Springer , Berlin . Wolfgang Thomas. 1997. Languages, automata, and logic. In Handbook of Formal Languages. Springer, Berlin."},{"key":"e_1_2_1_117_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(87)90108-3"},{"key":"e_1_2_1_118_1","series-title":"Lecture Notes in Computer Science, Oliver Boldt and Helmut J\u00fcrgensen (Eds.),Vol. 2214","volume-title":"Proceedings of the 4th International Workshop on Implementing Automata, Automata Implementation","author":"Trahtman Avraham N.","unstructured":"Avraham N. Trahtman . 2001. An algorithm to verify local threshold testability of deterministic finite automata . In Proceedings of the 4th International Workshop on Implementing Automata, Automata Implementation , Lecture Notes in Computer Science, Oliver Boldt and Helmut J\u00fcrgensen (Eds.),Vol. 2214 . Springer , Berlin , 164--173. Avraham N. Trahtman. 2001. An algorithm to verify local threshold testability of deterministic finite automata. In Proceedings of the 4th International Workshop on Implementing Automata, Automata Implementation, Lecture Notes in Computer Science, Oliver Boldt and Helmut J\u00fcrgensen (Eds.),Vol. 2214. Springer, Berlin, 164--173."},{"key":"e_1_2_1_119_1","doi-asserted-by":"publisher","DOI":"10.5555\/647900.760883"},{"key":"e_1_2_1_120_1","first-page":"326","article-title":"Finite automata and logic of monadic predicates","volume":"149","author":"Trakhtenbrot Boris A.","year":"1961","unstructured":"Boris A. Trakhtenbrot . 1961 . Finite automata and logic of monadic predicates . Doklady Akademii Nauk SSSR 149 (1961), 326 -- 329 . In Russian. Boris A. Trakhtenbrot. 1961. Finite automata and logic of monadic predicates. Doklady Akademii Nauk SSSR 149 (1961), 326--329. In Russian.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_1_121_1","series-title":"Lecture Notes in Computer Science, Jean-\u00c9ric Pin","volume-title":"Formal Properties of Finite Automata and Applications","author":"Weil Pascal","unstructured":"Pascal Weil . 1989. Concatenation product: A survey . In Formal Properties of Finite Automata and Applications . Lecture Notes in Computer Science, Jean-\u00c9ric Pin , Vol. 386 . Springer , Berlin , 120--137. Pascal Weil. 1989. Concatenation product: A survey. In Formal Properties of Finite Automata and Applications. Lecture Notes in Computer Science, Jean-\u00c9ric Pin, Vol. 386. Springer, Berlin, 120--137."},{"key":"e_1_2_1_122_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90151-5"},{"key":"e_1_2_1_123_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764895"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3303991","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3303991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:40Z","timestamp":1750204420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3303991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,13]]},"references-count":121,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3303991"],"URL":"https:\/\/doi.org\/10.1145\/3303991","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,13]]},"assertion":[{"value":"2016-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}