5 results
Thomas Place ; Marc Zeitoun.
An important endeavor in computer science is to understand the expressive power of logical formalisms over discrete structures, such as words. Naturally, "understanding" is not a mathematical notion. This investigation requires therefore a concrete objective to capture this understanding. In the […]
Published on July 20, 2018
Thomas Place.
We investigate a famous decision problem in automata theory: separation. Given a class of language C, the separation problem for C takes as input two regular languages and asks whether there exists a third one which belongs to C, includes the first one and is disjoint from the second. Typically, […]
Published on November 16, 2018
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 […]
Published on May 8, 2019
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 […]
Published on September 4, 2019
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 […]
Published on March 9, 2016