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