A New Pebble Game that Characterizes Parallel Complexity Classes
A New Pebble Game that Characterizes Parallel Complexity Classes
About this item
Full title
Author / Creator
Publisher
Philadelphia, PA: Society for Industrial and Applied Mathematics
Journal title
Language
English
Formats
Publication information
Publisher
Philadelphia, PA: Society for Industrial and Applied Mathematics
Subjects
More information
Scope and Contents
Contents
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 ${\text{AC}}^1 $. The characterizations show a fundamental way in...
Alternative Titles
Full title
A New Pebble Game that Characterizes Parallel Complexity Classes
Authors, Artists and Contributors
Author / Creator
Identifiers
Primary Identifiers
Record Identifier
TN_cdi_proquest_journals_919771909
Permalink
https://devfeature-collection.sl.nsw.gov.au/record/TN_cdi_proquest_journals_919771909
Other Identifiers
ISSN
0097-5397
E-ISSN
1095-7111
DOI
10.1137/0218036
