50 citations · 146 across the 25 of their papers we have counts for
4 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…
All about unambiguous polynomial closure
Thomas Place, Marc Zeitoun
We study a standard operator on classes of languages: unambiguous polynomial closure. We prove that for every class C of regular languages satisfying mild properties, the membershi…
Group separation strikes back
Thomas Place, Marc Zeitoun
Group languages are regular languages recognized by finite groups, or equivalently by finite automata in which each letter induces a permutation on the set of states. We investigat…
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…