Pebbling with an auxiliary pushdown

DOI10.1016/0022-0000(81)90011-8zbMATH Open0468.68067OpenAlexW2093998359MaRDI QIDQ1156489FDOQ1156489

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

• Superconcentrators
• Title not available (Why is that?)
• Tree-size bounded alternation
• Space bounds for a game on graphs
• Time-space trade-offs in a pebble game
• Title not available (Why is that?)

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)