Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

Deciding definability in FO2(<h,<v) on trees

Thomas Place ; Luc Segoufin.
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&nbsp;[&hellip;]
Published on September 1, 2015

A decidable characterization of locally testable tree languages

Thomas Place ; Luc Segoufin.
A regular tree language L is locally testable if membership of a tree in L depends only on the presence or absence of some fix set of neighborhoods in the tree. In this paper we show that it is decidable whether a regular tree language is locally testable. The decidability is shown for ranked trees&nbsp;[&hellip;]
Published on November 22, 2011

  • < Previous
  • 1
  • Next >