Search

• < Previous
• 1
• 2
• Next >

---

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;]

---

Piecewise testable tree languages

Mikołaj Bojańczyk ; Luc Segoufin ; Howard Straubing.

This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its&nbsp;[&hellip;]

---