More than being just a tool for expressing algorithms, a well-designed
programming language allows the user to express her ideas efficiently.
The design choices however effect the efficiency of the algorithms
written in the languages. It is therefore important to understand how
such choices effect the expressibility of programming languages.
The paper pursues the very low complexity programs by presenting a
first-order function algebra BC-varepsilon
that captures exactly logspace, the functions computable in
logarithmic space. This gives insights into the expressiveness of
recursion.
The important technical features of
BC-varepsilon are (1) a separation of
variables into safe and normal variables where recursion can only be
done over the latter; (2) linearity of the recursive call; and
(3) recursion with a variable step length (course-of-value
recursion). Unlike formulations of logspace via Turing
machines, BC-varepsilon makes no references
to outside resource measures, e.g., the size of the memory used.
This appears to be the first such characterization of
logspace-computable functions (not just predicates).
The proof that all BC-varepsilon-programs can
be evaluated in logspace is of separate interest to
programmers: it trades space for time and evaluates recursion with at
most one recursive call without a call stack.
[ 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.
