Back to Search
Start Over
Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
- Source :
- Information and Computation, Information and Computation, 2018, 248, pp.55-77, Lecture Notes in Computer Science, 8th IFIP International Conference on Theoretical Computer Science (TCS), 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.151-163, ⟨10.1007/978-3-662-44602-7_13⟩, Information and Computation, Elsevier, 2018, 248, pp.55-77, Advanced Information Systems Engineering ISBN: 9783642387081, IFIP TCS
- Publication Year :
- 2018
- Publisher :
- HAL CCSD, 2018.
-
Abstract
- Part 2: Track B: Logic, Semantics, Specification and Verification; International audience; In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for k ≥ 0, is given, by a type assignment system for a stratified λ-calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types.
- Subjects :
- Average-case complexity
Exponential complexity
Polynomial
[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO]
Linear logic
0102 computer and information sciences
Descriptive complexity theory
[INFO] Computer Science [cs]
Characterization (mathematics)
01 natural sciences
Theoretical Computer Science
Structural complexity theory
Computer Science::Logic in Computer Science
Complexity class
Lambda-calculus
[INFO]Computer Science [cs]
0101 mathematics
computer.programming_language
Mathematics
Discrete mathematics
Implicit computational complexity
Hierarchy (mathematics)
010102 general mathematics
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Computer Science Applications
Algebra
PH
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computational Theory and Mathematics
010201 computation theory & mathematics
Lambda calculus
computer
Quantum complexity theory
Information Systems
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-642-38708-1
- ISSN :
- 08905401 and 10902651
- ISBNs :
- 9783642387081
- Database :
- OpenAIRE
- Journal :
- Information and Computation, Information and Computation, 2018, 248, pp.55-77, Lecture Notes in Computer Science, 8th IFIP International Conference on Theoretical Computer Science (TCS), 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.151-163, ⟨10.1007/978-3-662-44602-7_13⟩, Information and Computation, Elsevier, 2018, 248, pp.55-77, Advanced Information Systems Engineering ISBN: 9783642387081, IFIP TCS
- Accession number :
- edsair.doi.dedup.....954c20417777d2caea1e00a09f25ff8a
- Full Text :
- https://doi.org/10.1007/978-3-662-44602-7_13⟩