A generic imperative language for polynomial time

arXiv1911.04026MaRDI QIDQ6328893FDOQ6328893

Authors: Daniel M. Leivant 

Publication date: 10 November 2019

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

This page was built for publication: A generic imperative language for polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328893)