50 citations · 111 across the 24 of their papers we have counts for
30 papers
Navigational hierarchies of regular languages
Thomas Place, Marc Zeitoun
We study the class of star-free languages. A long-standing goal is to classify them by the complexity of their descriptions. The most influential research effort involves concatena…
Dot-depth three, return of the J-class
Thomas Place, Marc Zeitoun
We look at concatenation hierarchies of classes of regular languages. Each such hierarchy is determined by a single class, its basis: level is built by applying the Boolean pol…
Closing star-free closure
Thomas Place, Marc Zeitoun
We introduce an operator on classes of regular languages, the star-free closure. Our motivation is to generalize standard results of automata theory within a unified framework. Giv…
A generic characterization of generalized unary temporal logic and two-variable first-order logic
Thomas Place, Marc Zeitoun
We investigate an operator on classes of languages. For each class , it outputs a new class associated with a variant of two-variable first-order logic equipped with…
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…