{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:52Z","timestamp":1753889752093,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:00:00Z","timestamp":1441065600000},"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 provide a decidable characterization of regular forest languages definable\nin FO2(&lt;h,&lt;v). By FO2(&lt;h,&lt;v) we refer to the two variable fragment of first\norder logic built from the descendant relation and the following sibling\nrelation. In terms of expressive power it corresponds to a fragment of the\nnavigational core of XPath that contains modalities for going up to some\nancestor, down to some descendant, left to some preceding sibling, and right to\nsome following sibling. We also show that our techniques can be applied to\nother two variable first-order logics having exactly the same vertical\nmodalities as FO2(&lt;h,&lt;v) but having different horizontal modalities.<\/jats:p>","DOI":"10.2168\/lmcs-11(3:5)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T13:46:02Z","timestamp":1479735962000},"source":"Crossref","is-referenced-by-count":0,"title":["Deciding definability in FO2(&lt;h,&lt;v) on trees"],"prefix":"10.46298","volume":"Volume 11, Issue 3","author":[{"given":"Thomas","family":"Place","sequence":"first","affiliation":[]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2015,9,1]]},"reference":[{"key":"923:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1581\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1581\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:07:15Z","timestamp":1681243635000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,1]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(3:5)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1505.04934","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1505.04934","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,9,1]]},"article-number":"1581"}}