arnold beckmann's pages
Notations for Exponentiation
Author: Arnold Beckmann
Title: Notations for Exponentiation
Journal: Theoretical Computer Science 2002, 288(1): 3-19
We define a coding of natural numbers — which we will
call the exponential notations — and interpretations of the
the successor function, addition and exponentiation on the exponential
We prove that all these interpretations are polynomial time computable.
As an application we show that we can interpret
terms over a certain restricted language — including exponentiation
— in polynomial time on exponential notations.