research-article

Open access

Raising expectations: automating expected cost analysis with types

Authors:

Jan HoffmannAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 4, Issue ICFP

Article No.: 110, Pages 1 - 31

https://doi.org/10.1145/3408992

Published: 03 August 2020 Publication History

Abstract

This article presents a type-based analysis for deriving upper bounds on the expected execution cost of probabilistic programs. The analysis is naturally compositional, parametric in the cost model, and supports higher-order functions and inductive data types. The derived bounds are multivariate polynomials that are functions of data structures. Bound inference is enabled by local type rules that reduce type inference to linear constraint solving. The type system is based on the potential method of amortized analysis and extends automatic amortized resource analysis (AARA) for deterministic programs. A main innovation is that bounds can contain symbolic probabilities, which may appear in data structures and function arguments. Another contribution is a novel soundness proof that establishes the correctness of the derived bounds with respect to a distribution-based operational cost semantics that also includes nontrivial diverging behavior. For cost models like time, derived bounds imply termination with probability one. To highlight the novel ideas, the presentation focuses on linear potential and a core language. However, the analysis is implemented as an extension of Resource Aware ML and supports polynomial bounds and user defined data structures. The effectiveness of the technique is evaluated by analyzing the sample complexity of discrete distributions and with a novel average-case estimation for deterministic programs that combines expected cost analysis with statistical methods.

Supplementary Material

Presentation at ICFP '20 (a110-wang-presentation.mp4)

Download
131.70 MB

References

[1]

E. Albert, P. Arenas, S. Genaim, M. Gómez-Zamalloa, G. Puebla, D. Ramírez, G. Román, and D. Zanardini. 2009. Termination and Cost Analysis with COSTA and its User Interfaces. Electr. Notes Theor. Comp. Sci. 258 ( December 2009 ). Issue 1.

[2]

E. Albert, J. C. Fernández, and G. Román-Díez. 2015. Non-cumulative Resource Analysis. In Tools and Algs. for the Construct. and Anal. of Syst. (TACAS'15).

[3]

R. Atkey. 2010. Amortised Resource Analysis with Separation Logic. In European Symp. on Programming (ESOP'10).

[4]

M. Avanzini, U. Dal Lago, and A. Ghyselen. 2019. Type-Based Complexity Analysis of Probabilistic Functional Programs. In Logic in Computer Science (LICS'19).

[5]

M. Avanzini, U. Dal Lago, and G. Moser. 2015. Analysing the Complexity of Functional Programs: Higher-Order Meets First-Order. In Int. Conf. on Functional Programming (ICFP'15).

[6]

M. Avanzini and G. Moser. 2013. A Combination Framework for Complexity. In Int. Conf. on Rewriting Techniques and Applications (RTA'13).

[7]

Ziv Bar-Yossef and Maxim Gurevich. 2008. Random sampling from a search engine's index. Journal of the ACM (JACM) 55, 5 ( 2008 ), 1-74.

Digital Library

[8]

G. Barthe, B. Grégoire, and S. Zanella Béguelin. 2009. Formal Certification of Code-based Cryptographic Proofs. In Princ. of Prog. Lang. (POPL'09).

[9]

G. Barthe, B. Köpf, F. Olmedo, and S. Zanella Béguelin. 2012. Probabilistic Relational Reasoning for Diferential Privacy. In Princ. of Prog. Lang. (POPL'12).

[10]

Kevin Batz, B. L. Kaminski, J.-P. Katoen, and C. Matheja. 2018. How long, O Bayesian network, will I sample thee?. In European Symp. on Programming (ESOP'18).

[11]

S. Bhat, A. Agarwal, R. Vuduc, and A. Gray. 2012. A Type Theory for Probability Density Functions. In Princ. of Prog. Lang. (POPL'12).

[12]

S. Bhat, J. Borgström, A. D. Gordon, and C. Russo. 2013. Deriving probability density functions from probabilistic functional programs. In Tools and Algs. for the Construct. and Anal. of Syst. (TACAS'13).

[13]

P. Billingsley. 2012. Probability and Measure. John Wiley & Sons, Inc.

[14]

R. Blanc, T. A. Henzinger, T. Hottelier, and L. Kovács. 2010. ABC: Algebraic Bound Computation for Loops. In Logic for Prog., AI., and Reasoning (LPAR'10).

Digital Library

[15]

J. Borgström, U. Dal Lago, A. D. Gordon, and M. Szymczak. 2016. A Lambda-Calculus Foundation for Universal Probabilistic Programming. In Int. Conf. on Functional Programming (ICFP'16).

[16]

M. Brockschmidt, F. Emmes, S. Falke, C. Fuhs, and J. Giesl. 2014. Alternating Runtime and Size Complexity Analysis of Integer Programs. In Tools and Algs. for the Construct. and Anal. of Syst. (TACAS'14).

[17]

J. Burnim, S. Juvekar, and K. Sen. 2009. WISE: Automated Test Generation for Worst-case Complexity. In Int. Conf. on Softw. Eng. (ICSE'09).

[18]

Q. Carbonneaux, J. Hofmann, T. Reps, and Z. Shao. 2017. Automated Resource Analysis with Coq Proof Objects. In Computer Aided Verif. (CAV'17).

[19]

Q. Carbonneaux, J. Hofmann, and Z. Shao. 2015. Compositional Certified Resource Bounds. In Prog. Lang. Design and Impl. (PLDI'15).

[20]

B. Carpenter, A. Gelman, M. D. Hofman, D. Lee, B. Goodrich, M. Betancourt, M. Brubaker, J. Guo, P. Li, and A. Riddell. 2017. Stan: A Probabilistic Programming Language. J. Statistical Softw. 76 ( 2017 ). Issue 1.

[21]

A. Charguéraud and F. Pottier. 2015. Machine-Checked Verification of the Correctness and Amortized Complexity of an Eficient Union-Find Implementation. In Interactive Theorem Proving (ITP'15).

[22]

K. Chatterjee, H. Fu, and A. K. Goharshady. 2016a. Termination Analysis of Probabilistic Programs Through Positivstellensatz's. In Computer Aided Verif. (CAV'16).

[23]

K. Chatterjee, H. Fu, P. Novotný, and R. Hasheminezhad. 2016b. Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Afine Probabilistic Programs. In Princ. of Prog. Lang. (POPL'16).

[24]

B. Chen, Y. Liu, and W. Le. 2016. Generating Performance Distributions via Probabilistic Symbolic Execution. In Int. Conf. on Softw. Eng. (ICSE'16).

[25]

E. Çiçek, G. Barthe, M. Gaboardi, D. Garg, and J. Hofmann. 2017. Relational Cost Analysis. In Princ. of Prog. Lang. (POPL'17).

[26]

E. Çiçek, D. Garg, and U. A. Acar. 2015. Refinement Types for Incremental Computational Complexity. In European Symp. on Programming (ESOP'15).

[27]

Edward A Codling, Michael J Plank, and Simon Benhamou. 2008. Random walk models in biology. Journal of the Royal Society Interface 5, 25 ( 2008 ), 813-834.

[28]

K. Crary and S. Weirich. 2000. Resource Bound Certification. In Princ. of Prog. Lang. (POPL'00).

[29]

J. Da Silva and J. G. Stefan. 2006. A Probabilistic Pointer Analysis for Speculative Optimizations. In Architectural Support for Prog. Lang. and Op. Syst. (ASPLOS'06).

[30]

U. Dal Lago and M. Gaboardi. 2011. Linear Dependent Types and Relative Completeness. In Logic in Computer Science (LICS'11).

[31]

U. Dal Lago and A. Ghyselen. 2018. On Linear Dependent Types and Probabilistic Termination. In International Workshop on Developments in Implicit Computational Complexity.

[32]

U. Dal Lago and C. Grellois. 2019. Probabilistic Termination by Monadic Afine Sized Typing. Trans. on Prog. Lang. and Syst. 41 ( June 2019 ). Issue 2.

[33]

U. Dal Lago and B. Petit. 2013. The Geometry of Types. In Princ. of Prog. Lang. (POPL'13).

[34]

N. A. Danielsson. 2008. Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures. In Princ. of Prog. Lang. (POPL'08).

[35]

N. Danner, D. R. Licata, and R. Ramyaa. 2015. Denotational Cost Semantics for Functional Languages with Inductive Types. In Int. Conf. on Functional Programming (ICFP'15).

[36]

D. Djuric. 2019. Billions of Random Numbers in a Blink of an Eye. Available on https://dragan.rocks/articles/19/Billionrandom-numbers-blink-eye-Clojure.

[37]

A. Filieri, C. S. Păsăreanu, and W. Visser. 2013. Reliability Analysis in Symbolic Pathfinder. In Int. Conf. on Softw. Eng. (ICSE'13).

[38]

A. Filieri, C. S. Păsăreanu, W. Visser, and J. Geldenhuys. 2014. Statistical Symbolic Execution with Informed Sampling. In Found. of Softw. Eng. (FSE'14).

[39]

A. Flores-Montoya and R. Hähnle. 2014. Resource Analysis of Complex Programs with Cost Equations. In Asian Symp. on Prog. Lang. and Systems (APLAS'14).

[40]

F. Frohn, M. Naaf, J. Hensel, M. Brockschmidt, and J. Giesl. 2016. Lower Runtime Bounds for Integer Programs. In Int. Joint Conf. on Automated Reasoning (IJCAR'16).

[41]

M. Gaboardi, A. Haeberlen, J. Hsu, A. Narayan, and B. C. Pierce. 2013. Linear Dependent Types for Diferential Privacy. In Princ. of Prog. Lang. (POPL'13).

[42]

N. D. Goodman and A. Stuhlmüller. 2014. The Design and Implementation of Probabilistic Programming Languages. Available on http://dippl.org.

[43]

Andrew D Gordon, Thomas A Henzinger, Aditya V Nori, and Sriram K Rajamani. 2014. Probabilistic programming. In Proceedings of the on Future of Software Engineering. 167-181.

Digital Library

[44]

S. Gulwani. 2009. SPEED: Symbolic Complexity Bound Analysis. In Computer Aided Verif. (CAV'09).

[45]

M. Hark, B. L. Kaminski, J. Giesl, and J.-P. Katoen. 2020. Aiming Low Is Harder: Induction for Lower Bounds in Probabilistic Program Verification. In Princ. of Prog. Lang. (POPL'20).

[46]

R. Harper. 2016. Practical Foundations for Programming Languages. Cambridge University Press.

Digital Library

[47]

J. Hofmann, K. Aehlig, and M. Hofmann. 2011. Multivariate Amortized Resource Analysis. In Princ. of Prog. Lang. (POPL'11).

[48]

J. Hofmann, A. Das, and S.-C. Weng. 2017. Towards Automatic Resource Bound Analysis for OCaml. In Princ. of Prog. Lang. (POPL'17).

[49]

J. Hofmann and M. Hofmann. 2010a. Amortized Resource Analysis with Polymorphic Recursion and Partial Big-Step Operational Semantics. In Asian Symp. on Prog. Lang. and Systems (APLAS'10).

[50]

J. Hofmann and M. Hofmann. 2010b. Amortized Resource Analysis with Polynomial Potential. In European Symp. on Programming (ESOP'10).

[51]

M. Hofmann and S. Jost. 2003. Static Prediction of Heap Space Usage for First-Order Functional Programs. In Princ. of Prog. Lang. (POPL'03).

[52]

M. Hofmann and G. Moser. 2015. Multivariate Amortised Resource Analysis for Term Rewrite Systems. In Int. Conf. on Typed Lambda Calculi and Applications (TLCA'15).

[53]

M. Hofmann and G. Moser. 2018. Analysis of Logarithmic Amortised Complexity. Technical Report. Computing Research Repository.

[54]

S. Jost, K. Hammond, H.-W. Loidl, and M. Hofmann. 2010. Static Determination of Quantitative Resource Usage for Higher-Order Programs. In Princ. of Prog. Lang. (POPL'10).

[55]

S. Jost, H.-W. Loidl, K. Hammond, N. Scaife, and M. Hofmann. 2009. Carbon Credits for Resource-Bounded Computations using Amortised Analysis. In Symp. on Form. Meth. (FM'09).

[56]

D. M. Kahn and J. Hofmann. 2020. Exponential Automatic Amortized Resource Analysis. In International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'20).

[57]

B. L. Kaminski, J.-P. Katoen, C. Matheja, and F. Olmedo. 2016. Weakest Precondition Reasoning for Expected Run-Times of Probabilistic Programs. In European Symp. on Programming (ESOP'16).

[58]

G. A. Kavvos, E. Morehouse, D. R. Licata, and N. Danner. 2020. Recurrence Extraction for Functional Programs through Call-by-Push-Value. In Princ. of Prog. Lang. (POPL'20).

[59]

Z. Kincaid, J. Breck, A. F. Boroujeni, and T. Reps. 2017. Compositional Recurrence Analysis Revisited. In Prog. Lang. Design and Impl. (PLDI'17).

[60]

T. Knoth, D. Wang, N. Polikarpova, and J. Hofmann. 2019. Resource-Guided Program Synthesis. In Prog. Lang. Design and Impl. (PLDI'19).

[61]

Donald Knuth and Andrew Yao. 1976. Algorithms and Complexity: New Directions and Recent Results, chapter The complexity of nonuniform random number generation.

[62]

D. Kozen. 1981. Semantics of Probabilistic Programs. J. Comput. Syst. Sci. 22 ( June 1981 ). Issue 3.

[63]

S. Kura, N. Urabe, and I. Hasuo. 2019. Tail Probability for Randomized Program Runtimes via Martingales for Higher Moments. In Tools and Algs. for the Construct. and Anal. of Syst. (TACAS'19).

[64]

A. K. Lew, M. F. Cusumano-Towner, B. Sherman, M. Carbin, and V. K. Mansinghka. 2020. Trace Types and Denotational Semantics for Sound Programmable Inference in Probabilistic Languages. In Princ. of Prog. Lang. (POPL'20).

[65]

Ch L MacLeod, Ž Ivezić, CS Kochanek, S Kozłowski, B Kelly, E Bullock, A Kimball, B Sesar, D Westman, K Brooks, et al. 2010. Modeling the time variability of SDSS stripe 82 quasars as a damped random walk. The Astrophysical Journal 721, 2 ( 2010 ), 1014.

[66]

V. K. Mansinghka, U. Schaechtle, S. Handa, A. Radul, Y. Chen, and M. C. Rinard. 2018. Probabilistic Programming with Programmable Inference. In Prog. Lang. Design and Impl. (PLDI'18).

[67]

A. K. McIver and C. C. Morgan. 2005. Abstraction, Refinement and Proof for Probabilistic Systems. Springer Science+Business Media, Inc.

[68]

Richard A Meese and Kenneth Rogof. 1983. Empirical exchange rate models of the seventies: Do they fit out of sample? Journal of international economics 14, 1-2 ( 1983 ), 3-24.

[69]

V. C. Ngo, Q. Carbonneaux, and J. Hofmann. 2018. Bounded Expectations: Resource Analysis for Probabilistic Programs. In Prog. Lang. Design and Impl. (PLDI'18).

[70]

V. C. Ngo, Mario Dehesa-Azuara, M. Fredrikson, and J. Hofmann. 2017. Verifying and Synthesizing Constant-Resource Implementations with Types. In Symp. on Sec. and Privacy (SP'17).

[71]

T. Nipkow. 2015. Amortized Complexity Verified. In Interactive Theorem Proving (ITP'15).

[72]

Y. Noller, R. Kersten, and C. S. Păsăreanu. 2018. Badger: Complexity Analysis with Fuzzing and Symbolic Execution. In Int. Symp. on Softw. Testing and Analysis (ISSTA'18).

[73]

L. Noschinski, F. Emmes, and J. Giesl. 2013. Analyzing Innermost Runtime Complexity of Term Rewriting by Dependency Pairs. J. Automated Reasoning 51 ( June 2013 ). Issue 1.

[74]

F. Olmedo, B. L. Kaminski, J.-P. Katoen, and C. Matheja. 2016. Reasoning about Recursive Probabilistic Programs. In Logic in Computer Science (LICS'16).

[75]

G. D. Plotkin. 1977. LCF Considered as a Programming Language. Theor. Comput. Sci. 5 ( 1977 ), 223-255.

[76]

I. Radicek, G. Barthe, M. Gaboardi, D. Garg, and F. Zuleger. 2018. Monadic Refinements for Relational Cost Analysis. In Princ. of Prog. Lang. (POPL'18).

[77]

G. Ramalingam. 1996. Data Flow Frequency Analysis. In Prog. Lang. Design and Impl. (PLDI'96).

[78]

J. Reed and B. C. Pierce. 2010. Distance Makes the Types Grow Stronger: A Calculus for Diferential Privacy. In Int. Conf. on Functional Programming (ICFP'10).

[79]

F. A. Saad, C. E. Freer, M. C. Rinard, and V. K. Mansinghka. 2020. Optimal Approximate Sampling from Discrete Probability Distributions. In Princ. of Prog. Lang. (POPL'20).

[80]

M. Sinn, F. Zuleger, and H. Veith. 2014. A Simple and Scalable Approach to Bound Analysis and Amortized Complexity Analysis. In Computer Aided Verif. (CAV'14).

[81]

R. E. Tarjan. 1985. Amortized Computational Complexity. SIAM J. Algebraic Discrete Methods 6 ( August 1985 ). Issue 2.

[82]

Joseph Tassarotti and Robert Harper. 2019. A Separation Logic for Concurrent Randomized Programs. Proc. ACM Program. Lang. 3, POPL, Article 64 ( Jan. 2019 ), 30 pages. https://doi.org/10.1145/3290377

Digital Library

[83]

P. B. Vasconcelos. 2008. Space Cost Analysis Using Sized Types. Ph.D. Dissertation. School of Computer Science, University of St Andrews.

[84]

Andre W Visser. 1997. Using random walk models to simulate the vertical distribution of particles in a turbulent water column. Marine Ecology Progress Series 158 ( 1997 ), 275-281.

[85]

D. Walker. 2002. Substructural Type Systems. In Advanced Topics in Types and Programming Languages. MIT Press.

[86]

D. Wang and J. Hofmann. 2019. Type-Guided Worst-Case Input Generation. In Princ. of Prog. Lang. (POPL'19).

[87]

Di Wang, Jan Hofmann, and Thomas Reps. 2020a. Tail Bound Analysis for Probabilistic Programs via Central Moments. arXiv: 2001. 10150 [cs.PL]

[88]

Di Wang, David M Kahn, and Jan Hofmann. 2020b. Raising Expectations: Automating Expected Cost Analysis with Types. arXiv: 2006. 14010 [cs.PL]

[89]

P. Wang, H. Fu, A. K. Goharshady, K. Chatterjee, X. Qin, and W. Shi. 2019. Cost Analysis of Nondeterministic Probabilistic Programs. In Prog. Lang. Design and Impl. (PLDI'19).

[90]

P. Wang, D. Wang, and A. Chlipala. 2017. TiML: A Functional Language for Practical Complexity Analysis with Invariants. In Object-Oriented Prog., Syst., Lang., and Applications (OOPSLA'17).

[91]

D. Williams. 1991. Probability with Martingales. Cambridge University Press.

[92]

D. Wingate and T. Weber. 2013. Automated Variational Inference in Probabilistic Programming. Technical Report. Computing Research Repository.

[93]

H. Xi. 2002. Dependent Types for Program Termination Verification. J. Higher-Order and Symbolic Comp. 15 ( 2002 ). Issue 1.

[94]

F. Zuleger, M. Sinn, S. Gulwani, and H. Veith. 2011. Bound Analysis of Imperative Programs with the Size-change Abstraction. In Static Analysis Symp. (SAS'11).

Digital Library

Cited By

Haselwarter PLi Kde Medeiros MGregersen SAguirre ATassarotti JBirkedal L(2024)Tachis: Higher-Order Separation Logic with Credits for Expected CostsProceedings of the ACM on Programming Languages10.1145/36897538:OOPSLA2(1189-1218)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689753
Rajani VBarthe GGarg D(2024)A Modal Type Theory of Expected Cost in Higher-Order Probabilistic ProgramsProceedings of the ACM on Programming Languages10.1145/36897258:OOPSLA2(389-414)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689725
Kura SUnno H(2024)Automated Verification of Higher-Order Probabilistic Programs via a Dependent Refinement Type SystemProceedings of the ACM on Programming Languages10.1145/36746628:ICFP(973-1002)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674662
Show More Cited By

Index Terms

Raising expectations: automating expected cost analysis with types
1. Theory of computation

Recommendations

On continuation-passing transformations and expected cost analysis

We define a continuation-passing style (CPS) translation for a typed λ-calculus with probabilistic choice, unbounded recursion, and a tick operator — for modeling cost. The target language is a (non-probabilistic) λ-calculus, enriched with a type of ...
Qualified types for MLF
Proceedings of the tenth ACM SIGPLAN international conference on Functional programming

MLF is a type system that extends a functional language with impredicative rank-n polymorphism. Type inference remains possible and only in some clearly defined situations, a local type annotation is required. Qualified types are a general concept that ...
Qualified types for MLF
ICFP '05: Proceedings of the tenth ACM SIGPLAN international conference on Functional programming

MLF is a type system that extends a functional language with impredicative rank-n polymorphism. Type inference remains possible and only in some clearly defined situations, a local type annotation is required. Qualified types are a general concept that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 4, Issue ICFP

August 2020

1070 pages

EISSN:2475-1421

DOI:10.1145/3415018

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 August 2020

Published in PACMPL Volume 4, Issue ICFP

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
541
Total Downloads

Downloads (Last 12 months)153
Downloads (Last 6 weeks)26

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Haselwarter PLi Kde Medeiros MGregersen SAguirre ATassarotti JBirkedal L(2024)Tachis: Higher-Order Separation Logic with Credits for Expected CostsProceedings of the ACM on Programming Languages10.1145/36897538:OOPSLA2(1189-1218)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689753
Rajani VBarthe GGarg D(2024)A Modal Type Theory of Expected Cost in Higher-Order Probabilistic ProgramsProceedings of the ACM on Programming Languages10.1145/36897258:OOPSLA2(389-414)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689725
Kura SUnno H(2024)Automated Verification of Higher-Order Probabilistic Programs via a Dependent Refinement Type SystemProceedings of the ACM on Programming Languages10.1145/36746628:ICFP(973-1002)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674662
Aguirre AHaselwarter Pde Medeiros MLi KGregersen STassarotti JBirkedal L(2024)Error Credits: Resourceful Reasoning about Error Bounds for Higher-Order Probabilistic ProgramsProceedings of the ACM on Programming Languages10.1145/36746358:ICFP(284-316)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674635
Gregersen SAguirre AHaselwarter PTassarotti JBirkedal L(2024)Almost-Sure Termination by Guarded RefinementProceedings of the ACM on Programming Languages10.1145/36746328:ICFP(203-233)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674632
Pham LSaad FHoffmann J(2024)Robust Resource Bounds with Static Analysis and Bayesian InferenceProceedings of the ACM on Programming Languages10.1145/36563808:PLDI(76-101)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656380
Avanzini MBarthe GGrégoire BMoser GVanoni G(2024)Hopping Proofs of Expectation-Based Properties: Applications to Skiplists and Security ProofsProceedings of the ACM on Programming Languages10.1145/36498398:OOPSLA1(784-809)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649839
Chatterjee KGoharshady AMeggendorfer TŽikelić Đ(2024)Quantitative Bounds on Resource Usage of Probabilistic ProgramsProceedings of the ACM on Programming Languages10.1145/36498248:OOPSLA1(362-391)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649824
Antonelli MDal Lago UPistone P(2024)Towards logical foundations for probabilistic computationAnnals of Pure and Applied Logic10.1016/j.apal.2023.103341175:9(103341)Online publication date: Oct-2024
https://doi.org/10.1016/j.apal.2023.103341
Kassing JDollase SGiesl J(2024)A Complete Dependency Pair Framework for Almost-Sure Innermost Termination of Probabilistic Term RewritingFunctional and Logic Programming10.1007/978-981-97-2300-3_4(62-80)Online publication date: 15-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2300-3_4
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents