Dexter Kozen, Rohit Parikh
Theoretical Computer Science
Conference paper
Pebblings, edgings, and equational logic
Abstract
A lower bound of ?(n/logn) space is shown for two natural proof systems for equational logic. The method introduces an edging game, a generalization of the pebble game [P].
Related
Conference paper
A new look at fault tolerant network routing
Danny Dolev, Joe Halpern, et al.
STOC 1984
Conference paper
Finding euler circuits in logarithmic parallel time
B. Awerbuch, A. Israeli, et al.
STOC 1984
Conference paper
FAST ALGORITHMS FOR N-DIMENSIONAL RESTRICTIONS OF HARD PROBLEMS.
Friedhelm Meyer auf der Heide
STOC 1984