7 citations · 7 across the 2 of their papers we have counts for
2 papers
cs.CC2009★ 7 cited
An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas
Olga Tveretina, Carsten Sinz, Hans Zantema
Haken proved that every resolution refutation of the pigeonhole formula has at least exponential size. Groote and Zantema proved that a particular OBDD computation of the pigeonhol…
cs.LO2009
Degrees of Undecidability in Rewriting
Joerg Endrullis, Herman Geuvers, Hans Zantema
Undecidability of various properties of first order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. Th…