50 citations · 111 across the 24 of their papers we have counts for
5 papers · 1 filter
Generic Results for Concatenation Hierarchies
Thomas Place, Marc Zeitoun
In the theory of formal languages, the understanding of concatenation hierarchies of regular languages is one of the most fundamental and challenging topic. In this paper, we surve…
Adding successor: A transfer theorem for separation and covering
Thomas Place, Marc Zeitoun
Given a class C of word languages, the C-separation problem asks for an algorithm that, given as input two regular languages, decides whether there exists a third language in C con…
Going Higher in First-Order Quantifier Alternation Hierarchies on Words
Thomas Place, Marc Zeitoun
We investigate quantifier alternation hierarchies in first-order logic on finite words. Levels in these hierarchies are defined by counting the number of quantifier alternations in…
The Covering Problem
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 m…
Separating regular languages with two quantifier alternations
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 whe…