Tropical Mathematics and the Lambda-Calculus II: Tropical Geometry of Probabilistic(…)
summary
Claims that each closed higher-order probabilistic bool program maps to a finite tropical degree and an associated minimal Newton polytope that encode its most-likely reduction runs, and that these can be estimated compositionally by an intersection-type proof system. Builds a concrete algorithm called VBby Newton multiplication to compute minimal products of polynomials (avoiding combinatorial blowup), proves the type system sound and complete for recovering the minimal Newton polytope, notes the tropical-degree decision problem is undecidable, and shows vertices yield retrievable most-likely traces via linear optimization.
AI-written summary · about