2020/08/11 by Thomas Ehrhard, Ehrhard, Thomas
Computer Science · #Advanced Algebra and Logic #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Programming Languages (cs.PL)
paper · pdf · doi:10.48550/arxiv.2008.04534
openalex publication_date 2020/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop a theory of probabilistic coherence spaces equipped with an additional extensional structure and apply it to approximating probability of convergence of ground type programs of probabilistic PCF whose free variables are of ground types. To this end we define an adapted version of Krivine Machine which computes polynomial approximations of the semantics of these programs in the model. These polynomials provide approximations from below and from above of probabilities of convergence; this is made possible by extending the language with an error symbol which is extensionally maximal in the model.