24 citations · 63 across the 14 of their papers we have counts for
7 papers · 1 filter
Regular languages defined by first-order formulas without quantifier alternation
Andreas Krebs, Howard Straubing
We give a simple new proof that regular languages defined by first-order sentences with no quantifier alteration can be defined by such sentences in which only regular atomic formu…
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership
Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya +1
We study two extensions of FO2[<], first-order logic interpreted in finite words, in which formulas are restricted to use only two variables. We adjoin to this language two-variabl…
Forest Categories
Howard Straubing
We extend Tilson's theory of the algebra of finite categories, in particular, the Derived Category Theorem, to the setting of forest algebras. As an illustration of the usefulness…
Two-variable Logic with a Between Predicate
Andreas Krebs, Kamal Lodaya, Paritosh Pandya +1
We study an extension of FO^2[<], first-order logic interpreted in finite words, in which formulas are restricted to use only two variables. We adjoin to this language two-variable…
EF+EX Forest Algebras
Andreas Krebs, Howard Straubing
We examine languages of unranked forests definable using the temporal operators EF and EX. We characterize the languages definable in this logic, and various fragments thereof, usi…
Wreath Products of Forest Algebras, with Applications to Tree Logics
Mikolaj Bojanczyk, Igor Walukiewicz, Howard Straubing
We use the recently developed theory of forest algebras to find algebraic characterizations of the languages of unranked trees and forests definable in various logics. These includ…
An effective characterization of the alternation hierarchy in two-variable logic
Andreas Krebs, Howard Straubing
We characterize the languages in the individual levels of the quantifier alternation hierarchy of first-order logic with two variables by identities. This implies decidability of t…