Peter Møller Neergaard
BC-epsilon: A recursion-theoretic characterization of
logspace
Technical report, Brandeis University, March 2004
Preliminary version
We present BC-epsilon which is a function algebra that is sound and
complete for logspace. It is based on the novel
recursion-theoretic principle of generalized recursion where the
step length of primitive recursion can be varied at each step. This
allows elegant representations of functions like logarithm and
division. Unlike characterizations found in the literature, it is
noticeable that there does not appear to be a way to represent pairs
in the algebra.
The soundness proof uses a simulation based on “computational
amnesia'' where, analogously to tail recursion optimization, a
recursive call replaces its own activation record. Even though the
call is not necessarily tail, we recover the full recursion by
repeatedly restarting the computation.
[ bib |
.ps.gz |
.pdf.gz |
.pdf ]
Back
This file has been generated by
bibtex2html 1.61
Copyright notice: The documents contained
in these pages are included by the contributing authors as a means to
ensure timely dissemination of scholarly and technical work on a
non-commercial basis. Copyright and all rights therein are maintained
by the authors or by other copyright holders, notwithstanding that
they have offered their works here electronically. It is understood that all persons copying this information will
adhere to the terms and constraints invoked by each author's
copyright. These works
may not be reposted without the explicit permission of the copyright
holder.
If you experience problems downloading any of the files above,
it is most likely because your browser does not handle compressed
files correctly.
In particular, Netscape might save the file in the compressed
gz-format with extension .ps or
.pdf (indicating postscript or PDF, resp.). You can work around this by saving the file,
renaming it to .ps.gz or .pdf.gz, and then
uncrompress it.
