4 citations · 9 across the 6 of their papers we have counts for
9 papers · 1 filter
The Join Levels of the Trotter-Weil Hierarchy are Decidable
Manfred Kufleitner, Alexander Lauser
The variety DA of finite monoids has a huge number of different characterizations, ranging from two-variable first-order logic FO^2 to unambiguous polynomials. In order to study th…
The Join of the Varieties of R-trivial and L-trivial Monoids via Combinatorics on Words
Manfred Kufleitner, Alexander Lauser
The join of two varieties is the smallest variety containing both. In finite semigroup theory, the varieties of R-trivial and L-trivial monoids are two of the most prominent classe…
Lattices of Logical Fragments over Words
Manfred Kufleitner, Alexander Lauser
This paper introduces an abstract notion of fragments of monadic second-order logic. This concept is based on purely syntactic closure properties. We show that over finite words, e…
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…
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…
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…