Non-determinism in Gödel's system \(T\)

DOI10.1007/s00224-011-9377-9zbMath1271.03049OpenAlexW2022103417MaRDI QIDQ693050

Lars Kristiansen, Bedeho Mesghina Wolde Mender

Publication date: 7 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9377-9

zbMATH Keywords

denotational semanticsnondeterminismcomplexity theoryGödel's System \(T\)

Mathematics Subject Classification ID

Logic in computer science (03B70) Semantics in the theory of computing (68Q55) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatory logic and lambda calculus (03B40)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)
• Classical recursion theory. Vol. II
• Relationships between nondeterministic and deterministic tape complexities
• Higher Types, Finite Domains and Resource-bounded Turing Machines
• Domain-Theoretic Foundations of Functional Programming
• Recursion in Higher Types and Resource Bounded Turing Machines
• Computer Science Logic
• New Computational Paradigms
• New Computational Paradigms
• Logical Approaches to Computational Barriers
• Theory and Applications of Models of Computation