A Rewriting Characterization of the Polynomial Space Functions


This talk is concerned with applications of rewriting techniques to
computational complexity classes. I talk about a rewriting characterization
of the class FPSPACE of functions computable in polynomial space obtained
in Eguchi (Proc. 10th Asian Logic Conference, 2010). We will consider a
schematic rewrite system R which captures FPSPACE in the following sense:
Every function from FPSPACE is representable as an instance of R.
Conversely, rewrite rules from R together with a suitable rewriting
strategy yield an algorithm which runs in polynomial space.