50 citations · 146 across the 25 of their papers we have counts for
31 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…
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…
Recognizing pro-R closures of regular languages
Jorge Almeida, José Carlos Costa, Marc Zeitoun
Given a regular language L, we effectively construct a unary semigroup that recognizes the topological closure of L in the free unary semigroup relative to the variety of unary sem…
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…
Separation for dot-depth two
Thomas Place, Marc Zeitoun
The dot-depth hierarchy of Brzozowski and Cohen classifies the star-free languages of finite words. By a theorem of McNaughton and Papert, these are also the first-order definable…
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…
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…
The Covering Problem
Thomas Place, Marc Zeitoun
An important endeavor in computer science is to understand the expressive power of logical formalisms over discrete structures, such as words. Naturally, "understanding" is not a m…
The linear nature of pseudowords
Jorge Almeida, Alfredo Costa, José Carlos Costa +1
Given a pseudoword over suitable pseudovarieties, we associate to it a labeled linear order determined by the factorizations of the pseudoword. We show that, in the case of the pse…
Quantifier Alternation for Infinite Words
Théo Pierron, Thomas Place, Marc Zeitoun
We investigate the expressive power of quantifier alternation hierarchy of first-order logic over words. This hierarchy includes the classes (sentences having at most blo…
Reducibility of pointlike problems
J. Almeida, J. C. Costa, M. Zeitoun
We show that the pointlike and the idempotent pointlike problems are reducible with respect to natural signatures in the following cases: the pseudovariety of all finite semigroups…
Factoriality and the Pin-Reutenauer procedure
J. Almeida, J. C. Costa, M. Zeitoun
We consider implicit signatures over finite semigroups determined by sets of pseudonatural numbers. We prove that, under relatively simple hypotheses on a pseudovariety V of semigr…
A Transfer Theorem for the Separation Problem
Thomas Place, Marc Zeitoun
We investigate two problems for a class C of regular word languages. The C-membership problem asks for an algorithm to decide whether an input language belongs to C. The C-separati…
A Characterization for Decidable Separability by Piecewise Testable Languages
Wojciech Czerwiński, Wim Martens, Lorijn van Rooijen +2
The separability problem for word languages of a class by languages of a class asks, for two given languages and from , whether the…