Search

• < Previous
• 1
• Next >

---

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

---

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

---

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

---

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

---

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

---