{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:58Z","timestamp":1753889818015,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,10,23]],"date-time":"2012-10-23T00:00:00Z","timestamp":1350950400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"name":"National Science Foundation","award":["0905276"],"award-info":[{"award-number":["0905276"]}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["233599"],"award-info":[{"award-number":["233599"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["2300131569"],"award-info":[{"award-number":["2300131569"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We consider a specific class of tree structures that can represent basic\nstructures in linguistics and computer science such as XML documents, parse\ntrees, and treebanks, namely, finite node-labeled sibling-ordered trees. We\npresent axiomatizations of the monadic second-order logic (MSO), monadic\ntransitive closure logic (FO(TC1)) and monadic least fixed-point logic\n(FO(LFP1)) theories of this class of structures. These logics can express\nimportant properties such as reachability. Using model-theoretic techniques, we\nshow by a uniform argument that these axiomatizations are complete, i.e., each\nformula that is valid on all finite trees is provable using our axioms. As a\nbackdrop to our positive results, on arbitrary structures, the logics that we\nstudy are known to be non-recursively axiomatizable.<\/jats:p>","DOI":"10.2168\/lmcs-8(4:12)2012","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T13:21:33Z","timestamp":1385731293000},"source":"Crossref","is-referenced-by-count":3,"title":["Complete Axiomatizations of Fragments of Monadic Second-Order Logic on Finite Trees"],"prefix":"10.46298","volume":"Volume 8, Issue 4","author":[{"given":"Am\u00e9lie","family":"Gheerbrant","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balder ten","family":"Cate","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2012,10,23]]},"reference":[{"key":"602:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1017\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1017\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:01:22Z","timestamp":1681243282000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,23]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(4:12)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1210.2620","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1210.2620","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1503.08936","asserted-by":"subject"},{"id-type":"doi","id":"10.1017\/jsl.2016.70","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1503.08936","asserted-by":"subject"},{"id-type":"handle","id":"11245.1\/1666f59f-65f7-45b5-b17d-a8974c46b554","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,10,23]]},"article-number":"1017"}}