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.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!