On the power of white pebbles (Q1180416): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01206359 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2611481948 / rank | |||
Normal rank |
Latest revision as of 10:01, 30 July 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