50 citations · 146 across the 25 of their papers we have counts for
5 papers · 1 filter
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…