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