5 papers
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…
Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth
Andreas Krebs, Oleg Verbitsky
Given a connected graph and its vertex , let denote the universal cover of obtained by unfolding into a tree starting from . Let be the minimum…
Streaming algorithms for recognizing nearly well-parenthesized expressions
Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2 when there are a few errors in the input string. 1-turn-Dyck2 with errors: We prove that there…
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…
Non-definability of languages by generalized first-order formulas over (N,+)
Andreas Krebs, A. V. Sreejith
We consider first-order logic with monoidal quantifiers over words. We show that all languages with a neutral letter, definable using the addition numerical predicate are also defi…