The Power of Non-determinism in Higher-Order Implicit Complexity

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

zbMATH Keywords

implicit computational complexitycons-free programmingEXPTIME hierarchynondeterministic programmingunitary variables

Mathematics Subject Classification ID

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