13 citations · 27 across the 5 of their papers we have counts for
9 papers
On all things star-free
Thomas Place, Marc Zeitoun
We investigate the star-free closure, which associates to a class of languages its closure under Boolean operations and marked concatenation. We prove that the star-free closure of…
Separation and covering for group based concatenation hierarchies
Thomas Place, Marc Zeitoun
Concatenation hierarchies are classifications of regular languages. All such hierarchies are built through the same construction process: start from an initial class of languages a…
The complexity of separation for levels in concatenation hierarchies
Thomas Place, Marc Zeitoun
We investigate the complexity of the separation problem associated to classes of regular languages. For a class C, C-separation takes two regular languages as input and asks whethe…
A generic characterization of Pol(C)
Thomas Place, Marc Zeitoun
We investigate the polynomial closure operation (C -> Pol(C)) defined on classes of regular languages. We present an interesting and useful connection relating the separation probl…
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…