Probabilistic Recursion Theory and Implicit Computational Complexity

DOI10.1007/978-3-319-10882-7_7zbMath1423.03137MaRDI QIDQ2938155

Ugo Dal Lago, Sara Zuppiroli

Publication date: 13 January 2015

Published in: Theoretical Aspects of Computing – ICTAC 2014 (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01091595/file/main.pdf

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

03D15: Complexity of computation (including implicit computational complexity)

03D10: Turing machines and related notions

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)