111 citations · 374 across the 31 of their papers we have counts for
33 papers · 1 filter
Completeness for Probabilistic Boolean Tapes
Filippo Bonchi, Cipriano Junior Cioffo
Probabilistic Boolean circuits have recently been proposed as a string-diagrammatic foundation for finite probabilistic programming. In this paper, we present a complete set of axi…
Diagrammatic Algebra of First Order Logic
Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon +1
We introduce the calculus of neo-Peircean relations, a string diagrammatic extension of the calculus of binary relations that has the same expressivity as first order logic and com…
Exploiting Adjoints in Property Directed Reachability Analysis
Mayuko Kori, Flavio Ascari, Filippo Bonchi +3
We formulate, in lattice-theoretic terms, two novel algorithms inspired by Bradley's property directed reachability algorithm. For finding safe invariants or counterexamples, the f…
Deconstructing the Calculus of Relations with Tape Diagrams
Filippo Bonchi, Alessandro Di Giorgio, Alessio Santamaria
Rig categories with finite biproducts are categories with two monoidal products, where one is a biproduct and the other distributes over it. In this work we present tape diagrams,…
String Diagram Rewrite Theory III: Confluence with and without Frobenius
Filippo Bonchi, Fabio Gadducci, Aleks Kissinger +2
In this paper we address the problem of proving confluence for string diagram rewriting, which was previously shown to be characterised combinatorically as double-pushout rewriting…
Convexity via Weak Distributive Laws
Filippo Bonchi, Alessio Santamaria
We study the canonical weak distributive law of the powerset monad over the semimodule monad for a certain class of semirings containing, in particular, positive semifields. Fo…
On Doctrines and Cartesian Bicategories
Filippo Bonchi, Alessio Santamaria, Jens Seeber +1
We study the relationship between cartesian bicategories and a specialisation of Lawvere's hyperdoctrines, namely elementary existential doctrines. Both provide different ways of a…
Diagrammatic Polyhedral Algebra
Filippo Bonchi, Alessandro Di Giorgio, Pawel Sobocinski
We extend the theory of Interacting Hopf algebras with an order primitive, and give a sound and complete axiomatisation of the prop of polyhedral cones. Next, we axiomatise an affi…
String Diagram Rewrite Theory II: Rewriting with Symmetric Monoidal Structure
Filippo Bonchi, Fabio Gadducci, Aleks Kissinger +2
Symmetric monoidal theories (SMTs) generalise algebraic theories in a way that make them suitable to express resource-sensitive systems, in which variables cannot be copied or disc…
String Diagram Rewrite Theory I: Rewriting with Frobenius Structure
Filippo Bonchi, Fabio Gadducci, Aleks Kissinger +2
String diagrams are a powerful and intuitive graphical syntax, originated in the study of symmetric monoidal categories. In the last few years, they have found application in the m…
Presenting convex sets of probability distributions by convex semilattices and unique bases
Filippo Bonchi, Ana Sokolova, Valeria Vignudelli
We prove that every finitely generated convex set of finitely supported probability distributions has a unique base, and use this result to show that the monad of convex sets of pr…
Cartesian bicategories with choice
Filippo Bonchi, Jens Seeber, Pawel Sobocinski
Relational structures are emerging as ubiquitous mathematical machinery in the semantics of open systems of various kinds. Cartesian bicategories are a well-known categorical algeb…
Contextual Equivalence for Signal Flow Graphs
Filippo Bonchi, Robin Piedeleu, Pawel Sobocinski +1
We extend the signal flow calculus---a compositional account of the classical signal flow graph model of computation---to encompass affine behaviour, and furnish it with a novel op…
Bialgebraic Semantics for String Diagrams
Filippo Bonchi, Robin Piedeleu, Pawel Sobocinski +1
Turi and Plotkin's bialgebraic semantics is an abstract approach to specifying the operational semantics of a system, by means of a distributive law between its syntax (encoded as…
Bisimilarity of Open Terms in Stream GSOS
Filippo Bonchi, Tom van Bussel, Matias David Lee +1
Stream GSOS is a specification format for operations and calculi on infinite sequences. The notion of bisimilarity provides a canonical proof technique for equivalence of closed te…
The Theory of Traces for Systems with Nondeterminism, Probability, and Termination
Filippo Bonchi, Ana Sokolova, Valeria Vignudelli
This paper studies trace-based equivalences for systems combining nondeterministic and probabilistic choices. We show how trace semantics for such processes can be recovered by ins…
Up-To Techniques for Behavioural Metrics via Fibrations
Filippo Bonchi, Barbara König, Daniela Petrisan
Up-to techniques are a well-known method for enhancing coinductive proofs of behavioural equivalences. We introduce up-to techniques for behavioural metrics between systems modelle…
Sound up-to techniques and Complete abstract domains
Filippo Bonchi, Pierre Ganty, Roberto Giacobazzi +1
Abstract interpretation is a method to automatically find invariants of programs or pieces of code whose semantics is given via least fixed-points. Up-to techniques have been intro…
Graphical Conjunctive Queries
Filippo Bonchi, Jens Seeber, Pawel Sobocinski
The Calculus of Conjunctive Queries (CCQ) has foundational status in database theory. A celebrated theorem of Chandra and Merlin states that CCQ query inclusion is decidable. Its p…
Coalgebraic Behavioral Metrics
Paolo Baldan, Filippo Bonchi, Henning Kerstan +1
We study different behavioral metrics, such as those arising from both branching and linear-time semantics, in a coalgebraic setting. Given a coalgebra for a fun…
Functorial Semantics for Relational Theories
Filippo Bonchi, Dusko Pavlovic, Pawel Sobocinski
We introduce the concept of Frobenius theory as a generalisation of Lawvere's functorial semantics approach to categorical universal algebra. Whereas the universe for models of Law…
Distribution Bisimilarity via the Power of Convex Algebras
Filippo Bonchi, Alexandra Silva, Ana Sokolova
Probabilistic automata (PA), also known as probabilistic nondeterministic labelled transition systems, combine probability and nondeterminism. They can be given different semantics…
Towards Trace Metrics via Functor Lifting
Paolo Baldan, Filippo Bonchi, Henning Kerstan +1
We investigate the possibility of deriving metric trace semantics in a coalgebraic framework. First, we generalize a technique for systematically lifting functors from the category…
Bialgebraic Semantics for Logic Programming
Filippo Bonchi, Fabio Zanasi
Bialgebrae provide an abstract framework encompassing the semantics of different kinds of computational models. In this paper we propose a bialgebraic approach to the semantics of…