An analysis of Bennett's pebble game
classification
🧮 math.CO
cs.CC
keywords
gamepebblebennettobtainrecursionspacetimeanalysis
pith:TFRZV4ML Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{TFRZV4ML}
Prints a linked pith:TFRZV4ML badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
Bennett's pebble game was introduced to obtain better time/space tradeoffs in the simulation of standard Turing machines by reversible ones. So far only upper bounds for the tradeoff based on the pebble game have been published. Here we give a recursion for the time optimal solution of the pebble game given a space bound. We analyze the recursion to obtain an explicit asymptotic expression for the best time-space product.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.