White pebbles help

DOI10.1016/0022-0000(88)90023-2MaRDI QIDQ1111025zbMATH OpenOpenAlexFDO

Authors Robert Wilber

Publication date 1988

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(88)90023-2

zbMATH Keywords

black-white pebblingcomputational complexitynondeterministic computationspebble gamestraight-line programs

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Formal languages and automata (68Q45)

Recommendations

• On the power of white pebbles
• An infinite pebble game and applications
• scientific article; zbMATH DE number 3976363
• The PSPACE-Completeness of Black-White Pebbling
• A tight bound for black and white pebbles on the pyramid

Cites work

• A comparison of two variations of a pebble game on graphs
• A tight bound for black and white pebbles on the pyramid
• An observation on time-storage trade off
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• scientific article; zbMATH DE number 3765164 (Why is no real title available?)
• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• scientific article; zbMATH DE number 3349780 (Why is no real title available?)
• Relationships between nondeterministic and deterministic tape complexities
• Storage requirements for deterministic polynomial time recognizable languages
• The space complexity of pebble games on trees

Cited in

(5)

• On the power of white pebbles
• A variation on the min cut linear arrangement problem
• Pebbling dynamic graphs in minimal space
• Pebble games and algebraic proof systems
• Pebble games and algebraic proof systems

This page was built for publication: White pebbles help

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111025)