13 citations · 20 across the 4 of their papers we have counts for
9 papers · 1 filter
A generic polynomial time approach to separation by first-order logic without quantifier alternation
Thomas Place, Marc Zeitoun
We look at classes of languages associated to the fragment of first-order logic BΣ1 which disallows quantifier alternations. Each class is defined by choosing the set of predicates…
Characterizing level one in group-based concatenation hierarchies
Thomas Place, Marc Zeitoun
We investigate two operators on classes of regular languages: polynomial closure (Pol) and Boolean closure (Bool). We apply these operators to classes of group languages G and to t…
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…