1 citations · 3 across the 4 of their papers we have counts for
4 papers · 1 filter
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 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…
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…