6 citations · 16 across the 14 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.LO2012
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
Given two structures and distinguishable in $\fo k$ (first-order logic with variables), let denote the minimum alternation depth of a $\fo k$ formula disting…
cs.LO2012★ 6 cited
Lower Bounds for Existential Pebble Games and k-Consistency Tests
Christoph Berkholz
The existential k-pebble game characterizes the expressive power of the existential-positive k-variable fragment of first-order logic on finite structures. The winner of the existe…
cs.LO2012
On the Complexity of Finding Narrow Proofs
Christoph Berkholz
We study the complexity of the following "resolution width problem": Does a given 3-CNF have a resolution refutation of width k? We prove that the problem cannot be decided in time…