The Power of Non-determinism in Higher-Order Implicit Complexity
From MaRDI portal
Publication:2988663
DOI10.1007/978-3-662-54434-1_25zbMath1485.68031OpenAlexW2580582392MaRDI QIDQ2988663
Jakob Grue Simonsen, Cynthia Kop
Publication date: 19 May 2017
Published in: Programming Languages and Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-54434-1_25
implicit computational complexitycons-free programmingEXPTIME hierarchynondeterministic programmingunitary variables
Theory of programming languages (68N15) Functional programming and lambda calculus (68N18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)
Related Items
Unnamed Item, Subclasses of \textsc{Ptime} interpreted by programming languages, Read/write factorizable programs, Unnamed Item, The Power of Non-determinism in Higher-Order Implicit Complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A recursion-theoretic approach to NP
- Non-determinism in Gödel's system \(T\)
- Characterizing complexity classes by higher type primitive recursive definitions
- A new recursion-theoretic characterization of the polytime functions
- Characterizing complexity classes by general recursive definitions in higher types
- On the computational complexity of imperative programming languages
- The expressive power of higher-order types or, life without CONS
- The Power of Non-determinism in Higher-Order Implicit Complexity
- A Short Introduction to Implicit Computational Complexity
- Some Programming Languages for Logspace and Ptime
- An analysis of ML typability
- An Implicit Characterization of the Polynomial-Time Decidable Sets by Cons-Free Rewriting
- Complexity Hierarchies and Higher-Order Cons-Free Rewriting.
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
