40 citations · 49 across the 10 of their papers we have counts for
3 papers · 1 filter
The strength of the dominance rule
Leszek Aleksander Kołodziejczyk, Neil Thapen
It has become standard that, when a SAT solver decides that a CNF is unsatisfiable, it produces a certificate of unsatisfiability in the form of a refutation of in some pro…
The logical strength of Büchi's decidability theorem
Leszek Kołodziejczyk, Henryk Michalewski, Cécilia Pradic +1
We study the strength of axioms needed to prove various results related to automata on infinite words and Büchi's theorem on the decidability of the MSO theory of . We…
Small Stone in Pool
Samuel R. Buss, Leszek Aleksander Kolodziejczyk
The Stone tautologies are known to have polynomial size resolution refutations and require exponential size regular refutations. We prove that the Stone tautologies also have polyn…