{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:07Z","timestamp":1753889707068,"version":"3.41.2"},"reference-count":3,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,8,14]],"date-time":"2012-08-14T00:00:00Z","timestamp":1344902400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We consider the class of languages defined in the 2-variable fragment of the\nfirst-order logic of the linear order. Many interesting characterizations of\nthis class are known, as well as the fact that restricting the number of\nquantifier alternations yields an infinite hierarchy whose levels are varieties\nof languages (and hence admit an algebraic characterization). Using this\nalgebraic approach, we show that the quantifier alternation hierarchy inside\nFO^{2}[&lt;] is decidable within one unit. For this purpose, we relate each level\nof the hierarchy with decidable varieties of languages, which can be defined in\nterms of iterated deterministic and co-deterministic products. A crucial notion\nin this process is that of condensed rankers, a refinement of the rankers of\nWeis and Immerman and the turtle languages of Schwentick, Th\\'erien and\nVollmer.<\/jats:p>","DOI":"10.2168\/lmcs-8(3:11)2012","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T08:17:46Z","timestamp":1385713066000},"source":"Crossref","is-referenced-by-count":8,"title":["On logical hierarchies within FO^2-definable languages"],"prefix":"10.46298","volume":"Volume 8, Issue 3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3869-416X","authenticated-orcid":false,"given":"Manfred","family":"Kufleitner","sequence":"first","affiliation":[]},{"given":"Pascal","family":"Weil","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,8,14]]},"reference":[{"key":"10.2168\/LMCS-8(3:11)2012_1","first-page":"296","volume":"4","author":"M. Adler and N. Immerman.","year":"2003","journal-title":"ACM Transactions on ComputationalLogic, 4:296\u0096314, 2003"},{"key":"10.2168\/LMCS-8(3:11)2012_2","doi-asserted-by":"crossref","unstructured":"J. Almeida. Finite Semigroups and Universal Algebra. World Scientific, Singapore, 1994.","DOI":"10.1142\/9789812831644"},{"key":"10.2168\/LMCS-8(3:11)2012_3","first-page":"96","volume":"88","author":"S. Cho and D. T. Huynh.","year":"1991","journal-title":"Theoretical Computer Science"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1212\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1212\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:05:59Z","timestamp":1681243559000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,14]]},"references-count":3,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(3:11)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1208.0713","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1208.0713","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,8,14]]},"article-number":"1212"}}