A Characterization of NC k by First Order Functional Programs

DOI10.1007/978-3-540-79228-4_12zbMath1139.68332OpenAlexW82168598MaRDI 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

Mathematics Subject Classification ID

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 (1)

Upper Bounds on Stream I/O Using Semantic Interpretations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A Characterization of NC k by First Order Functional Programs