Home // COMPUTATION TOOLS 2015, The Sixth International Conference on Computational Logics, Algebras, Programming, Tools, and Benchmarking // View article

A Specialized Recursive Language for Capturing Time-Space Complexity Classes

Authors:
Emanuele Covino
Giovanni Pani

Keywords: specialized computation languages, time-space classes, implicit computational complexity, predicative recursion

Abstract:
We provide a resource-free characterization of register machines that computes their output within polynomial time O(n^k), by defining our version of predicative recursion and of a related recursive programming language. Then, by means of some restriction on composition of programs, we define a programming language that characterize the register machines with a polynomial bound imposed over time and space complexity, simultaneously. A simple syntactical analysis allows us to evaluate the complexity of a program written in these languages.

Pages: 8 to 13

Copyright: Copyright (c) IARIA, 2015

Publication date: March 22, 2015

Published in: conference

ISSN: 2308-4170

ISBN: 978-1-61208-394-0

Location: Nice, France

Dates: from March 22, 2015 to March 27, 2015