13 citations · 19 across the 2 of their papers we have counts for
4 papers
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…
Separating regular languages by piecewise testable and unambiguous languages
Thomas Place, Lorijn van Rooijen, Marc Zeitoun
Separation is a classical problem asking whether, given two sets belonging to some class, it is possible to separate them by a set from a smaller class. We discuss the separation p…