On higher-order probabilistic subrecursion

MaRDI QIDQ5028447zbMATH OpenFDO

Authors Flavien Breuvart, Ugo Dal Lago, Agathe Herrou

Publication date 9 February 2022

Full work available at URL https://arxiv.org/abs/1701.04786, https://lmcs.episciences.org/8891

zbMATH Keywords

lambda calculusrandomized computationhigher-order recursion

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Combinatory logic and lambda calculus (03B40) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Semantics in the theory of computing (68Q55)

Recommendations

• On higher-order probabilistic subrecursion
• Probabilistic recursion theory and implicit computational complexity
• Probabilistic Recursion Theory and Implicit Computational Complexity
• On the termination problem for probabilistic higher-order recursive programs
• Probabilistic operational semantics for the lambda calculus

Cites work

• scientific article; zbMATH DE number 3889501 (Why is no real title available?)
• scientific article; zbMATH DE number 42059 (Why is no real title available?)
• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 3557236 (Why is no real title available?)
• scientific article; zbMATH DE number 3615887 (Why is no real title available?)
• scientific article; zbMATH DE number 1231645 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1408945 (Why is no real title available?)
• A Convenient Category for Higher-Order Probability Theory
• A higher-order characterization of probabilistic polynomial time
• Abstraction, Refinement and Proof for Probabilistic Systems
• Computational Complexity
• Computer vision. Models, learning, and inference. Foreword by Andrew Fitzgibbon.
• Lectures on the Curry-Howard isomorphism
• On probabilistic applicative bisimulation and call-by-value \(\lambda \)-calculi
• On the hardness of almost-sure termination
• Probabilistic Recursion Theory and Implicit Computational Complexity
• Probabilistic Turing Machines and Computability
• Probabilistic coherence spaces are fully abstract for probabilistic PCF
• Probabilistic operational semantics for the lambda calculus
• Probabilistic termination: soundness, completeness, and compositionality
• Semantics of probabilistic programs
• Term Rewriting and Applications
• The geometry of parallelism: classical, probabilistic, and quantum effects
• The typed lambda-calculus is not elementary recursive

Cited in

(4)

• Probabilistic recursion theory and implicit computational complexity
• On higher-order probabilistic subrecursion
• Subquadratic SNARGs in the random oracle model
• A higher-order characterization of probabilistic polynomial time

This page was built for publication: On higher-order probabilistic subrecursion

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