Pebblings, edgings, and equational logic

Dexter Kozen

doi:10.1145/800057.808709

STOC 1984

Conference paper

01 Dec 1984

Pebblings, edgings, and equational logic

View publication

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].

Paper

An elementary proof of the completeness of PDL

Dexter Kozen, Rohit Parikh

Theoretical Computer Science

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

View all publications

Abstract

Related

An elementary proof of the completeness of PDL

A new look at fault tolerant network routing

Finding euler circuits in logarithmic parallel time

FAST ALGORITHMS FOR N-DIMENSIONAL RESTRICTIONS OF HARD PROBLEMS.