Cost-Based Intuitionist Probabilities on Spaces of Graphs, Hypergraphs and Theorems
This provides a theoretical framework for probabilistic reasoning in graph theory and logic, though it appears incremental by building on existing foundations of inference and Heyting algebras.
The paper tackles the problem of defining probability measures on spaces of graphs, hypergraphs, and theorems by introducing a novel partial order based on transformation costs, resulting in an intuitionistic probability measure that extends to weighted rule systems in bicartesian closed categories.
A novel partial order is defined on the space of digraphs or hypergraphs, based on assessing the cost of producing a graph via a sequence of elementary transformations. Leveraging work by Knuth and Skilling on the foundations of inference, and the structure of Heyting algebras on graph space, this partial order is used to construct an intuitionistic probability measure that applies to either digraphs or hypergraphs. As logical inference steps can be represented as transformations on hypergraphs representing logical statements, this also yields an intuitionistic probability measure on spaces of theorems. The central result is also extended to yield intuitionistic probabilities based on more general weighted rule systems defined over bicartesian closed categories.