Non-determinism in Gödel's system T

DOI10.1007/S00224-011-9377-9MaRDI QIDQ693050zbMATH OpenOpenAlexFDO

Authors 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

complexity theorynondeterminismdenotational semanticsGödel's System \(T\)

Mathematics Subject Classification ID

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

Recommendations

• Non-determinism, non-termination and the strong normalization of System T
• Theory and Applications of Models of Computation
• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)
• Gödel's system T revisited
• Complexity of Gödel’s T in λ-Formulation

Cites work

• scientific article; zbMATH DE number 1215497 (Why is no real title available?)
• scientific article; zbMATH DE number 512793 (Why is no real title available?)
• scientific article; zbMATH DE number 3440411 (Why is no real title available?)
• Classical recursion theory. Vol. II
• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)
• Computer Science Logic
• Domain-Theoretic Foundations of Functional Programming
• Higher types, finite domains and resource-bounded Turing machines
• Logical Approaches to Computational Barriers
• New Computational Paradigms
• New Computational Paradigms
• Programming languages capturing complexity classes
• Recursion in Higher Types and Resource Bounded Turing Machines
• Relationships between nondeterministic and deterministic tape complexities
• Theory and Applications of Models of Computation

Cited in

(3)

• Theory and Applications of Models of Computation
• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)
• The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming

This page was built for publication: Non-determinism in Gödel's system \(T\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693050)