Pebbling with an auxiliary pushdown

DOI10.1016/0022-0000(81)90011-8zbMath0468.68067OpenAlexW2093998359MaRDI QIDQ1156489

Nicholas J. 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)

Related Items (2)

An infinite pebble game and applications ⋮ On uniform circuit complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Tree-size bounded alternation
• Time-space trade-offs in a pebble game
• Superconcentrators
• Space bounds for a game on graphs

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