4 citations · 9 across the 6 of their papers we have counts for
10 papers
Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
Manfred Kufleitner, Alexander Lauser
We consider the quantifier alternation hierarchy within two-variable first-order logic FO^2[<,suc] over finite words with linear order and binary successor predicate. We give a sin…
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…