{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:23:03Z","timestamp":1758709383521,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,9,19]],"date-time":"2012-09-19T00:00:00Z","timestamp":1348012800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"name":"National Science Foundation","award":["0915065"],"award-info":[{"award-number":["0915065"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We use the recently developed theory of forest algebras to find algebraic\ncharacterizations of the languages of unranked trees and forests definable in\nvarious logics. These include the temporal logics CTL and EF, and first-order\nlogic over the ancestor relation. While the characterizations are in general\nnon-effective, we are able to use them to formulate necessary conditions for\ndefinability and provide new proofs that a number of languages are not\ndefinable in these logics.<\/jats:p>","DOI":"10.2168\/lmcs-8(3:19)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":5,"title":["Wreath Products of Forest Algebras, with Applications to Tree Logics"],"prefix":"10.46298","volume":"Volume 8, Issue 3","author":[{"given":"Mikolaj","family":"Bojanczyk","sequence":"first","affiliation":[]},{"given":"Igor","family":"Walukiewicz","sequence":"additional","affiliation":[]},{"given":"Howard","family":"Straubing","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,9,19]]},"reference":[{"key":"516:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1215\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1215\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:06:05Z","timestamp":1681243565000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,19]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(3:19)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1208.6172","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1208.6172","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,9,19]]},"article-number":"1215"}}