Zvi Galil, Wolfgang J. Paul
Journal of the ACM
Paper
Hierarchies of complete problems
Abstract
An attempt is made to present a framework for the diverse complete problems that have been found. A new concept-a Hierarchy of Complete Problems is defined. Several hierarchies in various domains such as graph theory, automata theory, theorem proving and games are established. © 1976 Springer-Verlag.
Related
Conference paper
Fully dynamic planarity testing
Zvi Galil, Giuseppe F. Italiano, et al.
STOC 1992
Conference paper
Recognizing certain repetitions and reversals within strings
Zvi Galil, Joel Seiferas
FOCS 1976
Amir Averbuch, Zvi Galil, et al.
Theoretical Computer Science