50 citations · 111 across the 24 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.FL2019★ 1 cited
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…
cs.FL2019
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…
cs.FL2019★ 3 cited
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…