Search

• < Previous
• 1
• 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;]

---

Covering and separation for logical fragments with modular predicates

Thomas Place ; Varun Ramanathan ; Pascal Weil.

For every class $\mathscr{C}$ of word languages, one may associate a decision problem called $\mathscr{C}$-separation. Given two regular languages, it asks whether there exists a third language in $\mathscr{C}$ containing the first language, while being disjoint from the second one. Usually, finding&nbsp;[&hellip;]

---

Regular tree languages in low levels of the Wadge Hierarchy

Mikołaj Bojańczyk ; Filippo Cavallari ; Thomas Place ; Michał Skrzypczak.

In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the Boolean combinations of open sets&nbsp;[&hellip;]

---

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

---