Place, Thomas and Segoufin, Luc - Deciding definability in FO2(<h,<v) on trees

lmcs:1581 - Logical Methods in Computer Science, September 1, 2015, Volume 11, Issue 3
Deciding definability in FO2(<h,<v) on trees

Authors: Place, Thomas and Segoufin, Luc

We provide a decidable characterization of regular forest languages definable in FO2(<h,<v). By FO2(<h,<v) we refer to the two variable fragment of first order logic built from the descendant relation and the following sibling relation. In terms of expressive power it corresponds to a fragment of the navigational core of XPath that contains modalities for going up to some ancestor, down to some descendant, left to some preceding sibling, and right to some following sibling. We also show that our techniques can be applied to other two variable first-order logics having exactly the same vertical modalities as FO2(<h,<v) but having different horizontal modalities.


Source : oai:arXiv.org:1505.04934
DOI : 10.2168/LMCS-11(3:5)2015
Volume: Volume 11, Issue 3
Published on: September 1, 2015
Submitted on: October 11, 2013
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 129 times.
This article's PDF has been downloaded 24 times.