A Characterization of NC k by First Order Functional Programs
From MaRDI portal
Publication:3502640
DOI10.1007/978-3-540-79228-4_12zbMath1139.68332MaRDI QIDQ3502640
Jean-Yves Marion, Romain Péchoux
Publication date: 27 May 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_12
68N18: Functional programming and lambda calculus
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68N30: Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
Related Items
Cites Work
- Quasi-interpretations. A way to control resources
- On uniform circuit complexity
- Bounded linear logic: A modular approach to polynomial-time computability
- A new recursion-theoretic characterization of the polytime functions
- Light linear logic
- Function-algebraic characterizations of log and polylog parallel time
- Soft linear logic and polynomial time
- A characterization of alternating log time by ramified recurrence
- On uniformity within \(NC^ 1\)
- Resource Analysis by Sup-interpretation
- A Soft Type Assignment System for λ-Calculus
- Towards an Implicit Characterization of NC k
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Foundations of Software Science and Computation Structures
- A Characterization of Alternating Log Time by First Order Functional Programs
- Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
- New Computational Paradigms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
