4 citations · 9 across the 6 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
cs.FL2011
Around Dot-depth One
Manfred Kufleitner, Alexander Lauser
The dot-depth hierarchy is a classification of star-free languages. It is related to the quantifier alternation hierarchy of first-order logic over finite words. We consider fragme…
cs.FL2011
Regular Ideal Languages and Their Boolean Combinations
Franz Jahn, Manfred Kufleitner, Alexander Lauser
We consider ideals and Boolean combinations of ideals. For the regular languages within these classes we give expressively complete automaton models. In addition, we consider gener…
cs.FL2011
Languages of Dot-depth One over Infinite Words
Manfred Kufleitner, Alexander Lauser
Over finite words, languages of dot-depth one are expressively complete for alternation-free first-order logic. This fragment is also known as the Boolean closure of existential fi…