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 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.

Autore Pugliese

• Covino Emanuele , Pani Giovanni

Tutti gli autori

• COVINO E.;PANI G.

Titolo volume/Rivista

Non Disponibile

Anno di pubblicazione

2015

ISSN

Non Disponibile

ISBN

978-1-61208-394-0

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

Non Disponibile

Ultimo Aggiornamento Citazioni

Non Disponibile

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile