50 citations · 146 across the 25 of their papers we have counts for
25 papers · 1 filter
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…
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…
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…
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…
McCammond's normal forms for free aperiodic semigroups revisited
Jorge Almeida, José Carlos Costa, Marc Zeitoun
This paper revisits the solution of the word problem for -terms interpreted over finite aperiodic semigroups, obtained by J. McCammond. The original proof of correctness of McCa…
Going higher in the First-order Quantifier Alternation Hierarchy on Words
Thomas Place, Marc Zeitoun
We investigate the quantifier alternation hierarchy in first-order logic on finite words. Levels in this hierarchy are defined by counting the number of quantifier alternations in…
Separating Regular Languages with First-Order Logic
Thomas Place, Marc Zeitoun
Given two languages, a separator is a third language that contains the first one and is disjoint from the second one. We investigate the following decision problem: given two regul…
On Separation by Locally Testable and Locally Threshold Testable Languages
Thomas Place, Lorijn van Rooijen, Marc Zeitoun
A separator for two languages is a third language containing the first one and disjoint from the second one. We investigate the following decision problem: given two regular input…
Separating regular languages by piecewise testable and unambiguous languages
Thomas Place, Lorijn van Rooijen, Marc Zeitoun
Separation is a classical problem asking whether, given two sets belonging to some class, it is possible to separate them by a set from a smaller class. We discuss the separation p…