By careful analysis of the comparison map from a simplicial set to its image under Kan's ex-infinity functor we obtain a new and combinatorial proof that it is a weak homotopy equivalence. Moreover, ...we obtain a presentation of it as a strong anodyne extension. From this description we are able to quickly deduce some basic facts about ex-infinity and hence provide a new construction of the Kan-Quillen model structure on simplicial sets, which avoids the use of topological spaces or minimal fibrations.
Probability theory can be studied synthetically as the computational effect embodied by a commutative monad. In the recently proposed Markov categories, one works with an abstraction of the Kleisli ...category and then defines deterministic morphisms equationally in terms of copying and discarding. The resulting difference between 'pure' and 'deterministic' leads us to investigate the 'sober' objects for a probability monad, for which the two concepts coincide. We propose natural conditions on a probability monad which allow us to identify the sober objects and define an idempotent sobrification functor. Our framework applies to many examples of interest, including the Giry monad on measurable spaces, and allows us to sharpen a previously given version of de Finetti's theorem for Markov categories. This is an extended version of the paper accepted for the Logic In Computer Science (LICS) conference 2022. In this document we include more mathematical details, including all the proofs, of the statements and constructions given in the published version.
We study concrete sheaf models for a call-by-value higher-order language with recursion. Our family of sheaf models is a generalization of many examples from the literature, such as models for ...probabilistic and differentiable programming, and fully abstract logical relations models. We treat recursion in the spirit of synthetic domain theory. We provide a general construction of a lifting monad starting from a class of admissible monomorphisms in the site of the sheaf category. In this way, we obtain a family of models parametrized by a concrete site and a class of monomorphisms, for which we prove a general computational adequacy theorem.
We present a fully abstract model of a call-by-value language with higher-order functions, recursion and natural numbers, as an exponential ideal in a topos. Our model is inspired by the fully ...abstract models of O'Hearn, Riecke and Sandholm, and Marz and Streicher. In contrast with semantics based on cpo's, we treat recursion as just one feature in a model built by combining a choice of modular components.
Notions of computation can be modelled by monads. Algebraic effects offer a characterization of monads in terms of algebraic operations and equational axioms, where operations are basic programming ...features, such as reading or updating the state, and axioms specify observably equivalent expressions. However, many useful programming features depend on additional mechanisms such as delimited scopes or dynamically allocated resources. Such mechanisms can be supported via extensions to algebraic effects including scoped effects and parameterized algebraic theories. We present a fresh perspective on scoped effects by translation into a variation of parameterized algebraic theories. The translation enables a new approach to equational reasoning for scoped effects and gives rise to an alternative characterization of monads in terms of generators and equations involving both scoped and algebraic operations. We demonstrate the power of our fresh perspective by way of equational characterizations of several known models of scoped effects.
Computational effects are commonly modelled by monads, but often a monad can be presented by an algebraic theory of operations and equations. This talk is about monads and algebraic theories for ...languages for inference, and their connections to semirings and tensors. A basic class of examples of algebraic theories comes from considering the theory of modules for a semiring, e.g. the theory of unnormalized distributions, where the semiring is that of the non-negative real numbers. We propose that an interesting perspective is given by studying theories via semirings, and to this end explore several examples of subtheories of module theories, mostly relating to probability. Our main contribution concerns the commutative combination of effects, as studied by Hyland, Plotkin and Power: we observe that while the semiring tensor does not in general determine the tensor of subtheories of module theories, it still does in several fundamental probabilistic examples.
We study semantic models of probabilistic programming languages over graphs, and establish a connection to graphons from graph theory and combinatorics. We show that every well-behaved equational ...theory for our graph probabilistic programming language corresponds to a graphon, and conversely, every graphon arises in this way. We provide three constructions for showing that every graphon arises from an equational theory. The first is an abstract construction, using Markov categories and monoidal indeterminates. The second and third are more concrete. The second is in terms of traditional measure theoretic probability, which covers 'black-and-white' graphons. The third is in terms of probability monads on the nominal sets of Gabbay and Pitts. Specifically, we use a variation of nominal sets induced by the theory of graphs, which covers Erdős-Rényi graphons. In this way, we build new models of graph probabilistic programming from graphons.
We present two Dialectica-like constructions for models of intensional Martin-L\"of type theory based on G\"odel's original Dialectica interpretation and the Diller-Nahm variant, bringing dependent ...types to categorical proof theory. We set both constructions within a logical predicates style theory for display map categories where we show that 'quasifibred' versions of dependent products and universes suffice to construct their standard counterparts. To support the logic required for dependent products in the first construction, we propose a new semantic notion of finite sum for dependent types, generalizing finitely-complete extensive categories. The second avoids extensivity assumptions using biproducts in a Kleisli category for a fibred additive monad.
Objective: Biomedical data processing generally requires the secure stepwise transfer of sensitive personal information across multiple parties. Mediating such operations using distributed secure ...digital ledgers, i.e., blockchains, is investigated in this article. Materials and Methods: The bitmark property rights blockchain was used to simulate the process of assessing individuals for enrollment to specific clinical trials. In the scenario presented, a sponsor publishes a recruitment call for a clinical trial and patients signal their willingness to participate in the trial through blockchain transactions. The blockchain creates and maintains digital references of the medical data assets of prospective study participants as well as digital property certificates for assigning access rights to corresponding medical data assets. Trial matching services review the patient blockchain records and recommend study participants that are likely to meet the enrollment criteria of recruiting clinical trials. Digital certificates assign transient access rights to the data assets of the prospective study participants. These certificates are transferred to pertinent matching services and sponsors, allowing these organizations to examine the candidacy of each prospective study participant. Results: The trial matching simulation demonstrates that property rights blockchains can implement complicated multiparty interactions, such as those associated with medical data exchange, without supplemental peer-to-peer communications. Conclusions: Blockchain-based data marketplaces of the type described, when coupled with data-controlled virtual infrastructure environments (i.e., Medical Data Trusts), provide a viable model for managing the transfer, provenance, and processing of individual health information.
This thesis studies some constructions for building new models of Martin-Löf type theory out of old. We refer to the main techniques as gluing and idempotent splitting. For each we give general ...conditions under which type constructors exist in the resulting model. These techniques are used to construct some examples of Dialectica models of type theory. The name is chosen by analogy with de Paiva's Dialectica categories, which semantically embody Gödel's Dialectica functional interpretation and its variants. This continues a programme initiated by von Glehn with the construction of the polynomial model of type theory. We complete the analogy between this model and Gödel's original Dialectica by using our techniques to construct a two-level version of this model, equipping the original objects with an extra layer of predicates. In order to do this we have to carefully build up the theory of finite sum types in a display map category. We construct two other notable models. The first is a model analogous to the Diller-Nahm variant, which requires a detailed study of biproducts in categories of algebras. To make clear the generalization from the categories studied by de Paiva, we illustrate the construction of the Diller-Nahm category in terms of gluing an indexed system of types together with a system of predicates. Following this we develop the general techniques needed for the type-theoretic case. The second notable model is analogous to the Dialectica category associated to the error monad as studied by Biering. This model has only weak dependent products. In order to get a model with full dependent products we use the idempotent splitting construction, which generalizes the Karoubi envelope of a category. Making sense of the Karoubi envelope in the type-theoretic case requires us to face up to issues of coherence in our models. We choose the route of making sure all of the constructions we use preserve strict coherence, rather than applying a general coherence theorem to produce a strict model afterwards. Our chosen method preserves more detailed information in the final model.
