### arnold beckmann's pages

## Notations for Exponentiation

**File:** PDF-File

**Author:** Arnold Beckmann

**Title:** Notations for Exponentiation

**Journal:** Theoretical Computer Science 2002, **288**(1): 3-19

**DOI:** 10.1016/S0304-3975(01)00143-8

**Abstract:**
We define a coding of natural numbers — which we will
call the *exponential notations* — and interpretations of the
less-than-relation,
the successor function, addition and exponentiation on the exponential
notations.
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.