Content area

Abstract

Translate

The ramification method in Implicit Computational Complexity has been associated with functional programming, but adapting it to generic imperative programming is highly desirable, given the wider algorithmic applicability of imperative programming. We introduce a new approach to ramification which, among other benefits, adapts readily to fully general imperative programming. The novelty is in ramifying finite second-order objects, namely finite structures, rather than ramifying elements of free algebras. In so doing we bridge between Implicit Complexity's type theoretic characterizations of feasibility, and the data-flow approach of Static Analysis.

Details

1009240
Subject
Algorithms;
Canonical forms;
Complexity;
Imperative programming;
Programming languages;
Polynomials;
Recursive methods
Identifier / keyword
Logic in Computer Science; Computational Complexity; Programming Languages; Logic
URL
http://arxiv.org/abs/1911.04026
Title
A generic imperative language for polynomial time
Author
Leivant, Daniel
Publication title
arXiv.org; Ithaca
Publication year
2020
Publication date
Feb 19, 2020
Section
Computer Science; Mathematics
Publisher
Cornell University Library, arXiv.org
Source
arXiv.org
Place of publication
Ithaca
Country of publication
United States
University/institution
Cornell University Library arXiv.org
Publication subject
Biology, Statistics, Physics, Mathematics, Engineering--Electrical Engineering, Computers--Computer Engineering, Business And Economics--Banking And Finance
e-ISSN
2331-8422
Source type
Working Paper
Language of publication
English
Document type
Working Paper
Publication history
 
 
Online publication date
2020-02-20
Milestone dates
2019-11-11 (Submission v1); 2020-02-19 (Submission v2)
Publication history
 
 
   First posting date
20 Feb 2020
ProQuest document ID
2313804748
Document URL
https://www.proquest.com/working-papers/generic-imperative-language-polynomial-time/docview/2313804748/se-2?accountid=208611
Full text outside of ProQuest
http://arxiv.org/abs/1911.04026
Copyright
© 2020. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Last updated
2020-02-21
Database
ProQuest One Academic