6 citations · 12 across the 15 of their papers we have counts for
20 papers
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…
Wreath Products of Distributive Forest Algebras
Michael Hahn, Andreas Krebs, Howard Straubing
It is an open problem whether definability in Propositional Dynamic Logic (PDL) on forests is decidable. Based on an algebraic characterization by Bojańczyk, et. al.,(2012) in term…
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…
Difference hierarchies and duality with an application to formal languages
Célia Borlido, Mai Gehrke, Andreas Krebs +1
The notion of a difference hierarchy, first introduced by Hausdorff, plays an important role in many areas of mathematics, logic and theoretical computer science such as descriptiv…
Visibly Pushdown Languages and Free Profinite Algebras
Silke Czarnetzki, Andreas Krebs, Klaus-Jörn Lange
We build a notion of algebraic recognition for visibly pushdown languages by finite algebraic objects. These come with a typical Eilenberg relationship, now between classes of visi…
Team Semantics for the Specification and Verification of Hyperproperties
Andreas Krebs, Arne Meier, Jonni Virtema +1
We develop team semantics for Linear Temporal Logic (LTL) to express hyperproperties, which have recently been identified as a key concept in the verification of information flow p…