Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCartesian closed 2-categories and permutation equivalence in higher-order rewriting
179
0
0.0
(
0
)
Added by
Tom Hirschowitz
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Tom Hirschowitz
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The biologically inspired framework of port-graphs has been successfully used to specify complex systems. It is the basis of the PORGY modelling tool. To facilitate the specification of proof normalisation procedures via graph rewriting, in this paper we add higher-order features to the original port-graph syntax, along with a generalised notion of graph morphism. We provide a matching algorithm which enables to implement higher-order port-graph rewriting in PORGY, thus one can visually study the dynamics of the systems modelled. We illustrate the expressive power of higher-order port-graphs with examples taken from proof-net reduction systems.
We show that the techniques for resource control that have been developed in the so-called light logics can be fruitfully applied also to process algebras. In particular, we present a restriction of Higher-Order pi-calculus inspired by Soft Linear Logic. We prove that any soft process terminates in polynomial time. We argue that the class of soft processes may be naturally enlarged so that interesting processes are expressible, still maintaining the polynomial bound on executions.
Classical Processes (CP) is a calculus where the proof theory of classical linear logic types communicating processes with mobile channels, a la pi-calculus. Its construction builds on a recent propositions as types correspondence between session types and propositions in linear logic. Desirable properties such as type preservation under reductions and progress come for free from the metatheory of linear logic. We contribute to this research line by extending CP with code mobility. We generalise classical linear logic to capture higher-order (linear) reasoning on proofs, which yields a logical reconstruction of (a variant of) the Higher-Order pi-calculus (HOpi). The resulting calculus is called Classical Higher-Order Processes (CHOP). We explore the metatheory of CHOP, proving that its semantics enjoys type preservation and progress (terms do not get stuck). We also illustrate the expressivity of CHOP through examples, derivable syntax sugar, and an extension to multiparty sessions. Lastly, we define a translation from CHOP to CP, which encodes mobility of process code into reference passing.
We prove that every locally Cartesian closed $infty$-category with subobject classifier has a strict initial object and disjoint and universal binary coproducts.
We introduce an extension of Hoare logic for call-by-value higher-order functions with ML-like local reference generation. Local references may be generated dynamically and exported outside their scope, may store higher-order functions and may be used to construct complex mutable data structures. This primitive is captured logically using a predicate asserting reachability of a reference name from a possibly higher-order datum and quantifiers over hidden references. We explore the logics descriptive and reasoning power with non-trivial programming examples combining higher-order procedures and dynamically generated local state. Axioms for reachability and local invariant play a central role for reasoning about the examples.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
