Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHigher-order port-graph rewriting
145
0
0.0
(
0
)
Added by
EPTCS
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Maribel Fernandez
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 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.
Higher-order recursion schemes are recursive equations defining new operations from given ones called terminals. Every such recursion scheme is proved to have a least interpreted semantics in every Scotts model of lambda-calculus in which the terminals are interpreted as continuous operations. For the uninterpreted semantics based on infinite lambda-terms we follow the idea of Fiore, Plotkin and Turi and work in the category of sets in context, which are presheaves on the category of finite sets. Fiore et al showed how to capture the type of variable binding in lambda-calculus by an endofunctor Hlambda and they explained simultaneous substitution of lambda-terms by proving that the presheaf of lambda-terms is an initial Hlambda-monoid. Here we work with the presheaf of rational infinite lambda-terms and prove that this is an initial iterative Hlambda-monoid. We conclude that every guarded higher-order recursion scheme has a unique uninterpreted solution in this monoid.
Type-two constructions abound in cryptography: adversaries for encryption and authentication schemes, if active, are modeled as algorithms having access to oracles, i.e. as second-order algorithms. But how about making cryptographic schemes themselves higher-order? This paper gives an answer to this question, by first describing why higher-order cryptography is interesting as an object of study, then showing how the concept of probabilistic polynomial time algorithm can be generalized so as to encompass algorithms of order strictly higher than two, and finally proving some positive and negative results about the existence of higher-order cryptographic primitives, namely authentication schemes and pseudorandom functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
