1,721,203 research outputs found
Unique solutions of contractions, CCS, and their HOL formalisation
Full text linkThe unique solution of contractions is a proof technique for (weak) bisimilarity that overcomes certain syntactic limitations of Milner's “unique solution of equations” theorem. This paper presents an overview of a comprehensive formalisation of Milner's Calculus of Communicating Systems (CCS) in the HOL theorem prover (HOL4), with a focus towards the theory of unique solutions of equations and contractions. The formalisation consists of about 24,000 lines (1MB) of code in total. Some refinements of the “unique solution of contractions” theory itself are obtained. In particular we remove the constraints on summation, which must be guarded, by moving from contraction to rooted contraction. We prove the “unique solution of rooted contractions” theorem and show that rooted contraction is the coarsest precongruence contained in the contraction preorder
Extensional and Non-extensional Functions as Processes
Full text linkFollowing Milner's seminal paper, the representation of functions as processes has received considerable attention. For pure λ-calculus, the process representations yield (at best) non-extensional λ-theories (i.e., β rule holds, whereas η does not).In the paper, we study how to obtain extensional representations, and how to move between extensional and non-extensional representations. Using Internal π, Iπ (a subset of the π-calculus in which all outputs are bound), we develop a refinement of Milner's original encoding of functions as processes that is parametric on certain abstract components called wires. These are, intuitively, processes whose task is to connect two end-point channels. We show that when a few algebraic properties of wires hold, the encoding yields a λ-theory. Exploiting the symmetries and dualities of Iπ, we isolate three main classes of wires. The first two have a sequential behaviour and are dual of each other; the third has a parallel behaviour and is the dual of itself. We show the adoption of the parallel wires yields an extensional λ-theory; in fact, it yields an equality that coincides with that of Böhm trees with infinite η. In contrast, the other two classes of wires yield non-extensional λ-theories whose equalities are those of the Lévy-Longo and Böhm trees
Designing for mental health care ecosystems transformation: The role of a territorial co-lab for resources emergence and integration
Full text linkFarina, I., Sangiorgi, D., Bertotti, M. Torri, E. Dias, S. Marques, J. M. Alves, R. Adopting a co-design approach to foster collaborative capacity and reflexivity in Social Prescribing. A Service Ecosystem Design perspective. Linköping University Electronic Press
No full text
Modular coinduction up-to for higher-order languages via first-order transition systems
Full text linkThe bisimulation proof method can be enhanced by employing ‘bisimulations up-to’ techniques. A comprehensive theory of such enhancements has been developed for first-order (i.e., CCS-like) labelled transition systems (LTSs) and bisimilarity, based on abstract fixed-point theory and compatible functions. We transport this theory onto languages whose bisimilarity and LTS go beyond those of first-order models. The approach consists in exhibiting fully abstract translations of the more sophisticated LTSs and bisimilarities onto the first-order ones. This allows us to reuse directly the large corpus of up-to techniques that are available on first-order LTSs. The only ingredient that has to be manually supplied is the compatibility of basic up-to techniques that are specific to the new languages. We investigate the method on the π-calculus, the λ-calculus, and a (call-by-value) λ-calculus with references
On sequentiality and well-bracketing in the π-calculus
Full text linkThe π-calculus is used as a model for programming languages. Its cons exhibit arbitrary concurrency, making them very discriminating. This may prevent validating desirable behavioural equivalences in cases when more disciplined cons are expected.In this paper we focus on two such common disciplines: sequentiality, meaning that at any time there is a single thread of computation, and well-bracketing, meaning that calls to external services obey a stack-like discipline. We formalise the disciplines by means of type systems. The main focus of the paper is on studying the consequence of the disciplines on behavioural equivalence. We define and study labelled bisimilarities for sequentiality and well-bracketing. These relations are coarser than ordinary bisimilarity. We prove that they are sound for the respective (conual) barbed equivalence, and also complete under a certain technical condition.We show the usefulness of our techniques on a number of examples, that have mainly to do with the representation of functions and store
- …
