Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBinding bigraphs as symmetric monoidal closed theories
145
0
0.0
(
0
)
Added by
Tom Hirschowitz
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Authors
Tom Hirschowitz
Ask ChatGPT about the research
No Arabic abstract
Milners bigraphs are a general framework for reasoning about distributed and concurrent programming languages. Notably, it has been designed to encompass both the pi-calculus and the Ambient calculus. This paper is only concerned with bigraphical syntax: given what we here call a bigraphical signature K, Milner constructs a (pre-) category of bigraphs BBig(K), whose main features are (1) the presence of relative pushouts (RPOs), which makes them well-behaved w.r.t. bisimulations, and that (2) the so-called structural equations become equalities. Examples of the latter include, e.g., in pi and Ambient, renaming of bound variables, associativity and commutativity of parallel composition, or scope extrusion for restricted names. Also, bigraphs follow a scoping discipline ensuring that, roughly, bound variables never escape their scope. Here, we reconstruct bigraphs using a standard categorical tool: symmetric monoidal closed (SMC) theories. Our theory enforces the same scoping discipline as bigraphs, as a direct property of SMC structure. Furthermore, it elucidates the slightly mysterious status of so-called links in bigraphs. Finally, our category is also considerably larger than the category of bigraphs, notably encompassing in the same framework terms and a flexible form of higher-order contexts.
rate research
Read More
We define a notion of symmetric monoidal closed (SMC) theory, consisting of a SMC signature augmented with equations, and describe the classifying categories of such theories in terms of proof nets.
Applications of category theory often involve symmetric monoidal categories (SMCs), in which abstract processes or operations can be composed in series and parallel. However, in 2020 there remains a dearth of computational tools for working with SMCs. We present an unbiased approach to implementing symmetric monoidal categories, based on an operad of directed, acyclic wiring diagrams. Because the interchange law and other laws of a SMC hold identically in a wiring diagram, no rewrite rules are needed to compare diagrams. We discuss the mathematics of the operad of wiring diagrams, as well as its implementation in the software package Catlab.
We use Luries symmetric monoidal envelope functor to give two new descriptions of $infty$-operads: as certain symmetric monoidal $infty$-categories whose underlying symmetric monoidal $infty$-groupoids are free, and as certain symmetric monoidal $infty$-categories equipped with a symmetric monoidal functor to finite sets (with disjoint union as tensor product). The latter leads to a third description of $infty$-operads, as a localization of a presheaf $infty$-category, and we use this to give a simple proof of the equivalence between Luries and Barwicks models for $infty$-operads.
We present a hybrid dynamical type theory equipped with useful primitives for organizing and proving safety of navigational control algorithms. This type theory combines the framework of Fu--Kishida--Selinger for constructing linear dependent type theories from state-parameter fibrations with previous work on categories of hybrid systems under sequential composition. We also define a conjectural embedding of a fragment of linear-time temporal logic within our type theory, with the goal of obtaining interoperability with existing state-of-the-art tools for automatic controller synthesis from formal task specifications. As a case study, we use the type theory to organize and prove safety properties for an obstacle-avoiding navigation algorithm of Arslan--Koditschek as implemented by Vasilopoulos. Finally, we speculate on extensions of the type theory to deal with conjugacies between model and physical spaces, as well as hierarchical template-anchor relationships.
We propose a semantics for permutation equivalence in higher-order rewriting. This semantics takes place in cartesian closed 2-categories, and is proved sound and complete.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
