Probabilistic Programming Semantics for Name Generation
summary
Claims a concrete semantics: quasi-Borel spaces interpret the ν-calculus by mapping name generation to Gaussian sampling, and the model is fully abstract at first-order (not just ground types). Proof builds normal forms for the ν-calculus, uses descriptive set theory to rule out distinguishing predicates, and applies a measure-preserving group action on R to validate normalization in the model. Result is constructive and surprising: an off-the-shelf probabilistic model actually equals name generation at first-order.
AI-written summary · about