Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
5 results

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
Volume 7, Issue 4

On Separation by Locally Testable and Locally Threshold Testable Languages

Thomas Place ; Lorijn van Rooijen ; Marc Zeitoun.
A separator for two languages is a third language containing the first one and disjoint from the second one. We investigate the following decision problem: given two regular input languages, decide whether there exists a locally testable (resp. a locally threshold testable) separator. In both cases,&nbsp;[&hellip;]
Published on September 18, 2014
Volume 10, Issue 3

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
Volume 11, Issue 3

Separating Regular Languages with First-Order Logic

Thomas Place ; Marc Zeitoun.
Given two languages, a separator is a third language that contains the first one and is disjoint from the second one. We investigate the following decision problem: given two regular input languages of finite words, decide whether there exists a first-order definable separator. We prove that in&nbsp;[&hellip;]
Published on March 9, 2016
Volume 12, Issue 1

Separation for dot-depth two

Thomas Place ; Marc Zeitoun.
The dot-depth hierarchy of Brzozowski and Cohen classifies the star-free languages of finite words. By a theorem of McNaughton and Papert, these are also the first-order definable languages. The dot-depth rose to prominence following the work of Thomas, who proved an exact correspondence with the&nbsp;[&hellip;]
Published on September 17, 2021
Volume 17, Issue 3
  • < Previous
  • 1
  • Next >