On the power of white pebbles (Q1180416): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Storage requirements for deterministic polynomial time recognizable languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A tight bound for black and white pebbles on the pyramid / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Asymptotically tight bounds on time-space trade-offs in a pebble game / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A comparison of two variations of a pebble game on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Relationships between nondeterministic and deterministic tape complexities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: White pebbles help / rank | |||
Normal rank |
Revision as of 14:01, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the power of white pebbles |
scientific article |
Statements
On the power of white pebbles (English)
0 references
27 June 1992
0 references
Pebble games are played on directed acyclic graphs by placing and removing pebbles according to certain rules. The Black pebble game was introduced by Hewitt and Paterson to model the deterministic evaluation of straight-line programs where the pebbles correspond to the space used in the evaluation process. Cook and Sethi introduced the Black-White pebble game to model the nondeterministic evaluation of straight-line programs. The white pebbles are intended to model the nondeterministic choice. The rules of the Black pebble game are: (1) A black pebble may be placed on a vertex \(v\) if and only if all immediate predecessors of \(v\) have pebbles. (2) A black pebble can be removed from a vertex at any time. For the Black-White pebble game two extra rules are added: (3) A white pebble can be placed on a vertex at any time. (4) A white pebble can be removed from node \(v\) if and only if all immediage predecessors of \(v\) have pebbles. Starting with a pebble-free graph the goal is to pebble all the vertices while attempting to use as few pebbles as possible. A strategy is a sequence of moves that achieves this goal. By comparing the two games we learn about the trade-offs between nondeterminism and space resources. The authors construct a family of directed acyclic graphs \((G_ p | p)\) such that any Black pebble game strategy for \(G_ p\) requires \(p^ 2\) pebbles, whereas \(3p+1\) pebbles suffice when white pebbles are allowed.
0 references
determinism
0 references
directed acyclic graphs
0 references
pebble game
0 references
straight-line programs
0 references
nondeterminism
0 references