{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:36:01Z","timestamp":1750221361644,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,10,31]],"date-time":"2017-10-31T00:00:00Z","timestamp":1509408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG Emmy-Noether program KR","award":["4042\/2 (Krebs)"],"award-info":[{"award-number":["4042\/2 (Krebs)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>We give an algebraic characterization, based on the bilateral semidirect product of finite monoids, of the quantifier alternation hierarchy in two-variable first-order logic on finite words. As a consequence, we obtain a new proof that this hierarchy is strict. Moreover, by application of the theory of finite categories, we are able to make our characterization effective: that is, there is an algorithm for determining the exact quantifier alternation depth for a given language definable in two-variable logic.<\/jats:p>","DOI":"10.1145\/3149822","type":"journal-article","created":{"date-parts":[[2017,11,28]],"date-time":"2017-11-28T13:21:34Z","timestamp":1511875294000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic"],"prefix":"10.1145","volume":"18","author":[{"given":"Andreas","family":"Krebs","sequence":"first","affiliation":[{"name":"Wilhelm-Schickard-Institut, Universit\u00e4t T\u00fcbingen, Germany"}]},{"given":"Howard","family":"Straubing","sequence":"additional","affiliation":[{"name":"Computer Science Department, Boston College, Massachusetts, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,11,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Jorge Almeida. 1994. Finite Semigroups and Universal Algebra. World Scientific.  Jorge Almeida. 1994. Finite Semigroups and Universal Algebra. World Scientific.","DOI":"10.1142\/2481"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(96)00083-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90003-3"},{"volume-title":"Automata, Languages, and Machines","author":"Eilenberg Samuel","key":"e_1_2_1_4_1","unstructured":"Samuel Eilenberg . 1976. Automata, Languages, and Machines Vol. 2 . Academic Press . Samuel Eilenberg. 1976. Automata, Languages, and Machines Vol. 2. Academic Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Kousha Etessami Moshe Y. Vardi and Thomas Wilke. 1997. First-order logic with two variables and unary temporal logic. In LICS. 228--235.   Kousha Etessami Moshe Y. Vardi and Thomas Wilke. 1997. First-order logic with two variables and unary temporal logic. In LICS. 228--235.","DOI":"10.7146\/brics.v4i5.18784"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90055-2"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912)","author":"Krebs Andreas","year":"2012","unstructured":"Andreas Krebs and Howard Straubing . 2012 . An effective characterization of the alternation hierarchy in two-variable logic . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912) . 86--98. Andreas Krebs and Howard Straubing. 2012. An effective characterization of the alternation hierarchy in two-variable logic. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912). 86--98."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(67)80007-2"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","author":"Kufleitner Manfred","year":"2013","unstructured":"Manfred Kufleitner and Alexander Lauser . 2013 . Quantifier alternation in two-variable first-order logic with successor is decidable . In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913) . 305--316. Manfred Kufleitner and Alexander Lauser. 2013. Quantifier alternation in two-variable first-order logic with successor is decidable. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913). 305--316."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_44"},{"key":"e_1_2_1_12_1","unstructured":"Manfred Kufleitner and Pascal Weil. 2012. The FO2 alternation hierarchy is decidable. In Computer Science Logic. 426--439.  Manfred Kufleitner and Pascal Weil. 2012. The FO 2 alternation hierarchy is decidable. In Computer Science Logic. 426--439."},{"volume-title":"Varieties of Formal Languages","author":"Pin Jean-\u00c9ric","key":"e_1_2_1_13_1","unstructured":"Jean-\u00c9ric Pin . 1986. Varieties of Formal Languages . North Oxford Academic . Jean-\u00c9ric Pin. 1986. Varieties of Formal Languages. North Oxford Academic."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90137-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80020-X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02194921"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 5th International Conference on Developments in Language Theory (DLT\u201901)","author":"Schwentick Thomas","year":"2001","unstructured":"Thomas Schwentick , Denis Th\u00e9rien , and Heribert Vollmer . 2001 . Partially-ordered two-way automata: A new characterization of DA . In Proceedings of the 5th International Conference on Developments in Language Theory (DLT\u201901) , Revised Papers. 239--250. Thomas Schwentick, Denis Th\u00e9rien, and Heribert Vollmer. 2001. Partially-ordered two-way automata: A new characterization of DA. In Proceedings of the 5th International Conference on Developments in Language Theory (DLT\u201901), Revised Papers. 239--250."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Imre Simon. 1975. Piecewise testable events. In Automata Theory and Formal Languages. 214--222.   Imre Simon. 1975. Piecewise testable events. In Automata Theory and Formal Languages. 214--222.","DOI":"10.1007\/3-540-07407-4_23"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Howard Straubing. 1992. Circuit complexity and the expressive power of generalized first-order formulas. In ICALP. 16--27.   Howard Straubing. 1992. Circuit complexity and the expressive power of generalized first-order formulas. In ICALP. 16--27.","DOI":"10.1007\/3-540-55719-9_60"},{"key":"e_1_2_1_21_1","unstructured":"Howard Straubing. 2011. Algebraic characterization of the alternation hierarchy in FO2{&lt;} on finite words. In Computer Science Logic. 525--537.  Howard Straubing. 2011. Algebraic characterization of the alternation hierarchy in FO 2 {&lt;} on finite words. In Computer Science Logic. 525--537."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Howard Straubing and Denis Th\u00e9rien. 2002. Weakly iterated block products of finite monoids. In LATIN. 91--104.   Howard Straubing and Denis Th\u00e9rien. 2002. Weakly iterated block products of finite monoids. In LATIN. 91--104.","DOI":"10.1007\/3-540-45995-2_13"},{"key":"e_1_2_1_23_1","volume-title":"Semigroups, Algorithms, Automata and Languages, Coimbra (Portugal)","author":"Tesson Pascal","year":"2001","unstructured":"Pascal Tesson and Denis Th\u00e9rien . 2002. Diamonds are forever: The variety DA . In Semigroups, Algorithms, Automata and Languages, Coimbra (Portugal) 2001 . World Scientific , 475--500. Pascal Tesson and Denis Th\u00e9rien. 2002. Diamonds are forever: The variety DA. In Semigroups, Algorithms, Automata and Languages, Coimbra (Portugal) 2001. World Scientific, 475--500."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(91)90119-M"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276749"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(87)90108-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000120050033"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196702000912"},{"key":"e_1_2_1_29_1","volume-title":"Structure theorem and strict alternation hierarchy for FO2 on words. Logical Methods in Computer Science 5, 3","author":"Weis Philipp","year":"2009","unstructured":"Philipp Weis and Neil Immerman . 2009. Structure theorem and strict alternation hierarchy for FO2 on words. Logical Methods in Computer Science 5, 3 ( 2009 ). Philipp Weis and Neil Immerman. 2009. Structure theorem and strict alternation hierarchy for FO2 on words. Logical Methods in Computer Science 5, 3 (2009)."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3149822","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3149822","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:18Z","timestamp":1750213578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3149822"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,31]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3149822"],"URL":"https:\/\/doi.org\/10.1145\/3149822","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2017,10,31]]},"assertion":[{"value":"2016-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}