{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:32Z","timestamp":1760202572072,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2007,2,23]],"date-time":"2007-02-23T00:00:00Z","timestamp":1172188800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The study of finite automata and regular languages is a privileged meeting\npoint of algebra and logic. Since the work of Buchi, regular languages have\nbeen classified according to their descriptive complexity, i.e. the type of\nlogical formalism required to define them. The algebraic point of view on\nautomata is an essential complement of this classification: by providing\nalternative, algebraic characterizations for the classes, it often yields the\nonly opportunity for the design of algorithms that decide expressibility in\nsome logical fragment.\n  We survey the existing results relating the expressibility of regular\nlanguages in logical fragments of MSO[S] with algebraic properties of their\nminimal automata. In particular, we show that many of the best known results in\nthis area share the same underlying mechanics and rely on a very strong\nrelation between logical substitutions and block-products of pseudovarieties of\nmonoid. We also explain the impact of these connections on circuit complexity\ntheory.<\/jats:p>","DOI":"10.2168\/lmcs-3(1:4)2007","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T11:49:48Z","timestamp":1212493788000},"source":"Crossref","is-referenced-by-count":16,"title":["Logic Meets Algebra: the Case of Regular Languages"],"prefix":"10.46298","volume":"Volume 3, Issue 1","author":[{"given":"Pascal","family":"Tesson","sequence":"first","affiliation":[]},{"given":"Denis","family":"Therien","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2007,2,23]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2226\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2226\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:09:57Z","timestamp":1681243797000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,23]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-3(1:4)2007","relation":{"is-same-as":[{"id-type":"arxiv","id":"cs\/0701154","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0701154","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"doi","id":"10.1007\/11874683_28","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2007,2,23]]},"article-number":"2226"}}