Pebbling with an auxiliary pushdown

DOI10.1016/0022-0000(81)90011-8MaRDI QIDQ1156489zbMATHOpenAlexFDO

Authors Nicholas Pippenger

Publication date 1981

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(81)90011-8

zbMATH Keywords

pebble gameauxiliary pushdown machinesworst-case time-space trade-off

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• scientific article; zbMATH DE number 3453572 (Why is no real title available?)
• Space bounds for a game on graphs
• Superconcentrators
• Time-space trade-offs in a pebble game
• Tree-size bounded alternation

Cited in

(2)

• An infinite pebble game and applications
• On uniform circuit complexity

This page was built for publication: Pebbling with an auxiliary pushdown

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