A new pebble game that characterizes parallel complexity classes
H Venkateswaran, M Tompa - SIAM Journal on Computing, 1989 - SIAM
H Venkateswaran, M Tompa
SIAM Journal on Computing, 1989•SIAMA new two-person pebble game that models parallel computations is defined. This game
extends the two-person pebble game defined by Dymond and Tompa J. Comput. System
Sci., 30 (1985), pp. 149–161 and is used to characterize two natural parallel complexity
classes, namely LOGCFL and AC^1. The characterizations show a fundamental way in
which the computations in these two classes differ. This game model also unifies the proofs
of some well-known results of complexity theory.
extends the two-person pebble game defined by Dymond and Tompa J. Comput. System
Sci., 30 (1985), pp. 149–161 and is used to characterize two natural parallel complexity
classes, namely LOGCFL and AC^1. The characterizations show a fundamental way in
which the computations in these two classes differ. This game model also unifies the proofs
of some well-known results of complexity theory.
A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined by Dymond and Tompa [J. Comput. System Sci., 30 (1985), pp. 149–161] and is used to characterize two natural parallel complexity classes, namely LOGCFL and . The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well-known results of complexity theory.
Showing the best result for this search. See all results