اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCartesian closed 2-categories and permutation equivalence in higher-order rewriting
166
0
0.0
(
0
)
تأليف
Tom Hirschowitz
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 pape
r 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 Lo
gic. 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 typ
es 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 use
d 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
