People increasingly use digital platforms to exchange resources in accordance with some policies stating what resources users offer and what they require in return. In this paper, we propose a formal model of these environments, focussing on how users' policies are defined and enforced, so ensuring that malicious users cannot take advantage of honest ones. To that end, we introduce the declarative policy language MuAC and equip it with a formal semantics. To determine if a resource exchange is fair, i.e., if it respects the MuAC policies in force, we introduce the non-standard logic MuACL that combines non-linear, linear and contractual aspects, and prove it decidable. Notably, the operator for contractual implication of MuACL is not expressible in linear logic. We define a semantics preserving compilation of MuAC policies into MuACL, thus establishing that exchange fairness is reduced to finding a proof in MuACL. Finally, we show how this approach can be put to work on a blockchain to exchange non-fungible tokens.

In multiagent systems autonomous agents interact with each other to achieve individual and collective goals. Typical interactions concern negotiation and agreement on resource exchanges. Modeling and formalizing these agreements pose significant challenges, particularly in capturing the dynamic behaviour of agents, while ensuring that resources are correctly handled. Here, we propose exchange environments as a formal setting where agents specify and obey exchange policies, which are declarative statements about what resources they offer and what they require in return. Furthermore, we introduce a decidable extension of the computational fragment of linear logic as a fundamental tool for representing exchange environments and studying their dynamics in terms of provability.

Security Enhanced Linux (SELinux) is a security architecture for Linux implementing Mandatory Access Control. It has been used in numerous security-critical contexts ranging from servers to mobile devices. However, its application is challenging as SELinux security policies are difficult to write, understand, and maintain. Recently, the intermediate language CIL was introduced to foster the development of high-level policy languages and to write structured configurations. Despite CIL’s high level features, CIL configurations are hard to understand as different constructs interact in non-trivial ways. Moreover, there is no mechanism to ensure that a given configuration obeys desired information flow policies. To remedy this, we enrich CIL with a formal semantics, and we propose IFCIL, a backward compatible extension of CIL for specifying fine-grained information flow requirements. Using IFCIL, administrators can express confidentiality, integrity, and non-interference properties. We also provide a tool to statically verify these requirements and we experimentally assess it on ten real-world policies.

Physical layer security mechanisms use primitives that exploit physical properties of the communication channel to protect data. Protecting communications at the physical layer offers some advantages, e.g., in terms of reduced computations, since complex cryptographic procedures are not executed, However, these mechanisms lack a formal specification that prevent protocols and applications that use them from being verified and compared with those based on cyptography. Here we start filling this gap by providing an axiomatization of key physical layer security primitives and proposing a variant of the Dolev–Yao attacker model that takes them into account. We show that our formalization enables applying existing automatic tools for verifying security of protocols. Then, we show that these primitives are a valuable alternative and effective complement to cryptography, because they ensure confidentiality and integrity but require a lower energy consumption and often they also reduce transmission time. Finally, we characterize the specific application domains and network features that make adopting these security mechanisms particularly profitable with respect to the AES cypher.

Security Enhanced Linux (SELinux) is a security architecture for Linux implementing mandatory access control. It has been used in numerous security-critical contexts ranging from servers to mobile devices. But this is challenging as SELinux security policies are difficult to write, understand, and maintain. Recently, the intermediate language CIL was introduced to foster the development of high-level policy languages and to write structured configurations. However, CIL lacks mechanisms for ensuring that the resulting configurations obey desired information flow policies. To remedy this, we propose IFCIL, a backward compatible extension of CIL for specifying fine-grained information flow requirements for CIL configurations. Using IFCIL, administrators can express, e.g., confidentiality, integrity, and non-interference properties. We also provide a tool to statically verify these requirements.

Firewalls are essential for managing and protecting computer networks. They permit specifying which packets are allowed to enter a network, and also how these packets are modified by IP address translation and port redirection. Configuring a firewall is notoriously hard, and one of the reasons is that it requires using low level, hard to interpret, configuration languages. Equally difficult are policy maintenance and refactoring, as well as porting a configuration from one firewall system to another. To address these issues we introduce a pipeline that assists system administrators in checking if: (i) the intended security policy is actually implemented by a configuration; (ii) two configurations are equivalent; (iii) updates have the desired effect on the firewall behavior; (iv) there are useless or redundant rules; additionally, an administrator can (v) transcompile a configuration into an equivalent one in a different language; and (vi) maintain a configuration using a generic, declarative language that can be compiled into different target languages. The pipeline is based on IFCL, an intermediate firewall language equipped with a formal semantics, and it is implemented in an open source tool called FWS. In particular, the first stage decompiles real firewall configurations for iptables, ipfw, pf and (a subset of) Cisco IOS into IFCL. The second one transforms an IFCL configuration into a logical predicate and uses the Z3 solver to synthesize an abstract specification that succinctly represents the firewall behavior. System administrators can use FWS to analyze the firewall by posing SQL-like queries, and update the configuration to meet the desired security requirements. Finally, the last stage allows for maintaining a configuration by acting directly on its abstract specification and then compiling it to the chosen target language. Tests on real firewall configurations show that FWS can be fruitfully used in real-world scenarios.

Computer systems often provide hardware support for isolation mechanisms such as privilege levels, virtual memory, or enclaved execution. Over the past years, several successful software-based side-channel attacks have been developed that break, or at least significantly weaken, the isolation that these mechanisms offer. Extending a processor with new architectural or micro-architectural features brings a risk of introducing new software-based side-channel attacks. This article studies the problem of extending a processor with new features without weakening the security of the isolation mechanisms that the processor offers. Our solution is heavily based on techniques from research on programming languages. More specifically, we propose to use the programming language concept of full abstraction as a general formal criterion for the security of a processor extension. We instantiate the proposed criterion to the concrete case of extending a microprocessor that supports enclaved execution with secure interruptibility. This is a very relevant instantiation, as several recent papers have shown that interruptibility of enclaves leads to a variety of software-based side-channel attacks. We propose a design for interruptible enclaves and prove that it satisfies our security criterion. We also implement the design on an open-source enclave-enabled microprocessor and evaluate the cost of our design in terms of performance and hardware size.

Computer systems often provide hardware support for isolation mechanisms like privilege levels, virtual memory, or enclaved execution. Over the past years, several successful software-based side-channel attacks have been developed that break, or at least significantly weaken the isolation that these mechanisms offer. Extending a processor with new architectural or micro-architectural features, brings a risk of introducing new such side-channel attacks. This paper studies the problem of extending a processor with new features without weakening the security of the isolation mechanisms that the processor offers. We propose to use full abstraction as a formal criterion for the security of a processor extension, and we instantiate that criterion to the concrete case of extending a microprocessor that supports enclaved execution with secure interruptibility of these enclaves. This is a very relevant instantiation as several recent papers have shown that interruptibility of enclaves leads to a variety of software-based side-channel attacks. We propose a design for interruptible enclaves, and prove that it satisfies our security criterion. We also implement the design on an open-source enclave-enabled microprocessor, and evaluate the cost of our design in terms of performance and hardware size.

Abstract Verifying the correctness of a system as a whole requires establishing that it satisfies a global specification. When it does not, it would be helpful to determine which modules are incorrect. As a consequence, specification decomposition is a relevant problem from both a theoretical and practical point of view. Until now, specification decomposition has been independently addressed by the control theory and verification communities throughnatural projectionandpartial model checking, respectively. We prove that natural projection reduces to partial model checking and, when cast in a common setting, the two are equivalent. Apart from their foundational interest, our results build a bridge whereby the control theory community can reuse algorithms and results developed by the verification community. Furthermore, we extend the notions of natural projection and partial model checking from finite-state to symbolic transition systems and we show that the equivalence still holds. Symbolic transition systems are more expressive than traditional finite-state transition systems, as they can model large systems, whose behavior depends on the data handled, and not only on the control flow. Finally, we present an algorithm for the partial model checking of both kinds of systems that can be used as an alternative to natural projection.

Service contracts characterise the desired behavioural compliance of a composition of services. Compliance is typically defined by the fulfilment of all service requests through service offers, as dictated by a given Service-Level Agreement (SLA). Contract automata are a recently introduced formalism for specifying and composing service contracts. Based on the notion of synthesis of the most permissive controller from Supervisory Control Theory, a safe orchestration of contract automata can be computed that refines a composition into a compliant one. To model more fine-grained SLA and more adaptive service orchestrations, in this paper we endow contract automata with two orthogonal layers of variability: (i) at the structural level, constraints over service requests and offers define different configurations of a contract automaton, depending on which requests and offers are selected or discarded, and (ii) at the behavioural level, service requests of different levels of criticality can be declared, which induces the novel notion of semi-controllability. The synthesis of orchestrations is thus extended to respect both the structural and the behavioural variability constraints. Finally, we show how to efficiently compute the orchestration of all configurations from only a subset of these configurations. A prototypical tool supports the developed theory.

Configuring and maintaining a firewall configuration is notoriously hard. Policies are written in low-level, platform-specific languages where firewall rules are inspected and enforced along non trivial control flow paths. Further difficulties arise from Network Address Translation (NAT), since filters must be implemented with addresses translations in mind. In this work, we study the problem of decompiling a real firewall configuration into an abstract specification. This abstract version throws the low-level details away by exposing the meaning of the configuration, i.e., the allowed connections with possible address translations. The generated specification makes it easier for system administrators to check if: (i) the intended security policy is actually implemented; (ii) two configurations are equivalent; (iii) updates have the desired effect on the firewall behavior. The peculiarity of our approach is that is independent of the specific target firewall system and language. This independence is obtained through a generic intermediate language that provides the typical features of real configuration languages and that separates the specification of the rulesets, determining the destiny of packets, from the specification of the platform-dependent steps needed to elaborate packets. We present a tool that decompiles real firewall configurations from different systems into this intermediate language and uses the Z3 solver to synthesize the abstract specification that succinctly represents the firewall behavior and the NAT. Tests on real configurations show that the tool is effective: it synthesizes complex policies in a matter of minutes and, and it answers to specific queries in just a few seconds. The tool can also point out policy differences before and after configuration updates in a simple, tabular form.

The Internet of Things (IoT) offers the infrastructure of the information society. It hosts smart objects that automatically collect and exchange data of various kinds, directly gathered from sensors or generated by aggregations. Suitable coordination primitives and analysis mechanisms are in order to design and reason about IoT systems, and to intercept the implied technological shifts. We address these issues from a foundational point of view. To study them, we define IoT-LySa, a process calculus endowed with a static analysis that tracks the provenance and the manipulation of IoT data, and how they flow in the system. The results of the analysis can be used by a designer to check the behaviour of smart objects, in particular to verify non-functional properties, among which security.

Adaptive systems improve their efficiency by modifying their behaviour to respond to changes in their operational environment. Also, security must adapt to these changes and policy enforcement becomes dependent on the dynamic contexts. We study these issues within [Formula: see text], (the core of) an adaptive declarative language proposed recently. A main characteristic of [Formula: see text] is to have two components: a logical one for handling the context and a functional one for computing. We extend this language with security policies that are expressed in logical terms. They are of two different kinds: context and application policies. The first, unknown a priori to an application, protect the context from unwanted changes. The others protect the applications from malicious actions of the context, can be nested and can be activated and deactivated according to their scope. An execution step can only occur if all the policies in force hold, under the control of an execution monitor. Beneficial to this is a type and effect system, which safely approximates the behaviour of an application, and a further static analysis, based on the computed effect. The last analysis can only be carried on at load time, when the execution context is known, and it enables us to efficiently enforce the security policies on the code execution, by instrumenting applications. The monitor is thus implemented within [Formula: see text], and it is only activated on those policies that may be infringed, and switched off otherwise.

Adaptive systems are designed to modify their behaviour in response to changes of their operational environment. We propose a two-component language for adaptive programming, within the Context-Oriented Programming paradigm. It has a declarative constituent for programming the context and a functional one for computing. We equip our language with a dynamic formal semantics. Since wrong adaptation could severely compromise the correct behaviour of applications and violate their properties, we also introduce a two-phase verification mechanism. It is based on a type and effect system that type-checks programs and computes, as an effect, a sound approximation of their behaviour. The effect is exploited at load time to mechanically verify that programs correctly adapt themselves to all possible running environments.

Abstract Differential privacy aims at protecting the privacy of participants in statistical databases. Roughly, a mechanism satisfies differential privacy if the presence or value of a single individual in the database does not significantly change the likelihood of obtaining a certain answer to any statistical query posed by a data analyst. Differentially-private mechanisms are often oblivious: first the query is processed on the database to produce a true answer, and then this answer is adequately randomized before being reported to the data analyst. Ideally, a mechanism should minimize leakage – i.e., obfuscate as much as possible the link between reported answers and individuals’ data – while maximizing utility – i.e., report answers as similar as possible to the true ones. These two goals, however, are in conflict with each other, thus imposing a trade-off between privacy and utility. In this paper we use quantitative information flow principles to analyze leakage and utility in oblivious differentially-private mechanisms. We introduce a technique that exploits graph symmetries of the adjacency relation on databases to derive bounds on the min-entropy leakage of the mechanism. We consider a notion of utility based on identity gain functions, which is closely related to min-entropy leakage, and we derive bounds for it. Finally, given some graph symmetries, we provide a mechanism that maximizes utility while preserving the required level of differential privacy.

We study usage automata, a formal model for specifying policies on the usage of resources. Usage automata extend finite state automata with some additional features, parameters and guards, that improve their expressivity. We show that usage automata are expressive enough to model policies of real-world applications. We discuss their expressive power, and we prove that the problem of telling whether a computation complies with a usage policy is decidable. The main contribution of this paper is a model checking technique for usage automata. The model is that of usages, i.e. basic processes that describe the possible patterns of resource access and creation. In spite of the model having infinite states, because of recursion and resource creation, we devise a polynomial-time model checking technique for deciding when a usage complies with a usage policy.

This special issue is devoted to various areas in Theoretical Computer Science. The issue took \ninspiration from the 13th Italian Conference on Theoretical Computer Science (ICTCS 2012), held at \nUniversity of Insubria in Varese, Italy, on September 19-21 2012. The special issue contains seven \npapers, that have been originated from the work in progress presented at the conference, and that have \nbeen accepted for publication after a rigorous review process and revisions. \nWe kindly thank all the authors of the published papers, as well as all the participants to ICTCS 2012, \nwho make it such an exciting event. \nWe are very grateful to the referees who devoted their precious time to produce thorough reviews. \nTheir valuable comments and suggestions improved a lot the submitted manuscripts. \nWe are especially thankful to Professor Damian Niwinski, Editor-in-Chief of Fundamenta Informaticae, \nfor accepting this special issue and for his help throughout the publication process. \nLastly, we wish to dedicate this special issue to the memory of Professor Alberto Bertoni, who was \none of the co-founders of the Italian chapter of the European Association for Theoretical Computer \nScience, and passed away on February 2014.

The issue took inspiration from the conference on Principles of Security and Trust (POST

Service Oriented Computing (SOC) is a programming paradigm aiming at characterising Service Networks. Services are entities waiting for requests from clients and they often result from the composition of many (sub-)services. We address here the probl

A type flaw attack on a security protocol is an attack where an honest principal is cheated on interpreting a field in a message as the one with a type other than the intended one. In this paper, we shall present an extension of the LYSA calculus to cope with types, by using tags to represent the i ntended types of terms. We develop a Control Flow Analysis for this calculus which soundly over-approximates all the possible behaviour of a protocol and, in particular, is able to capture any type confusion that may occur during the protocol execution. The analysis acts in a descriptive way: it describes which violations may occur. In the same setting, our approach also offers a prescriptive usage: we can impose a type discipline, by forcing some data to be of the expected types. At this point, the analysis may statically check that type violations are not possible any longer. In other words, we instrument the code with the only checks necessary to enforce type security. Finally, we apply our framework to a multi-protocol setting, where the risk of having type flaw attacks is higher. Our analysis has been implemented and successfully applied to a number of security protocols, showing it is able to capture type flaw attacks. The implementation complexity of the analysis is low polynomial.

A static approach is proposed to study secure composition of services. We extend the λ-calculus with primitives for selecting and invoking services that respect given security requirements. Security-critical code is enclosed in policy framings with a possibly nested, local scope. Policy framings en force safety and liveness properties. The actual run-time behaviour of services is over-approximated by a type and effect system. Types are standard, and effects include the actions with possible security concerns – as well as information about which services may be invoked at run-time. An approximation is model checked to verify policy framings within their scopes. This allows for removing any run-time execution monitor, and for determining the plans driving the selection of those services that match the security requirements on demand.

An extension of the λ-calculus is proposed, to study resource usage analysis and verification. It features usage policies with a possibly nested, local scope, and dynamic creation of resources. We define a type and effect system that, given a program, extracts a history expression, that is, a sound overapproximation to the set of histories obtainable at runtime. After a suitable transformation, history expressions are model-checked for validity. A program is resource-safe if its history expression is verified valid: If such, no runtime monitor is needed to safely drive its executions.

BACKGROUND: Research in life sciences is benefiting from a large availability of formal description techniques and analysis methodologies. These allow both the phenomena investigated to be precisely modeled and virtual experiments to be performed in silico. Such experiments may result in easier, faster, and satisfying approximations of their in vitro/vivo counterparts. A promising approach is represented by the study of biological phenomena as a collection of interactive entities through process calculi equipped with stochastic semantics. These exploit formal grounds developed in the theory of concurrency in computer science, account for the not continuous, nor discrete, nature of many phenomena, enjoy nice compositional properties and allow for simulations that have been demonstrated to be coherent with data in literature. RESULTS: Motivated by the need to address some aspects of the functioning of neural synapses, we have developed one such model for synaptic processes in the calyx of Held, which is a glutamatergic synapse in the auditory pathway of the mammalia. We have developed such a stochastic model starting from existing kinetic models based on ODEs of some sub-components of the synapse, integrating other data from literature and making some assumptions about non-fully understood processes. Experiments have confirmed the coherence of our model with known biological data, also validating the assumptions made. Our model overcomes some limitations of the kinetic ones and, to our knowledge, represents the first model of synaptic processes based on process calculi. The compositionality of the approach has permitted us to independently focus on tuning the models of the pre- and post- synaptic traits, and then to naturally connect them, by dealing with "interface" issues. Furthermore, we have improved the expressiveness of the model, e.g. by embedding easy control of element concentration time courses. Sensitivity analysis over several parameters of the model has provided results that may help clarify the dynamics of synaptic transmission, while experiments with the model of the complete synapse seem worth explaining short-term plasticity mechanisms. CONCLUSIONS: Specific presynaptic and postsynaptic mechanisms can be further analysed under various conditions, for instance by studying the presynaptic behaviour under repeated activations. The level of details of the description can be refined, for instance by further specifying the neurotransmitter generation and release steps. Taking advantage of the compositionality of the approach, an enhanced model could then be composed with other neural models, designed within the same framework, in order to obtain a more detailed and comprehensive model. In the long term, we are interested, in particular, in addressing models of synaptic plasticity, i.e. activity dependent mechanisms, which are the bases of memory and learning processes. More on the computer science side, we plan to follow some directions to improve the underlying computational model and the linguistic primitives it provides as suggested by the experiments carried out, e.g. by introducing a suitable notion of (spatial) locality.

We outline a methodology for designing and composing services in a secure manner. In particular, we are concerned with safety properties of service behaviour. Services can enforce security policies locally and can invoke other services respecting given security contracts. This call-by-contract mechanism offers a significant set of opportunities, each driving secure ways to compose services. We discuss how to correctly plan services compositions in several relevant classes of services and security properties. To this aim, we propose a graphical modelling framework, based on a foundational calculus called lambda-req. Our formalism features dynamic and static semantics, so allowing for formal reasoning about systems. Static analysis and model checking techniques provide the designer with useful information to assess and fix possible vulnerabilities.

Comparative genomics usually involves managing the functional aspects of genomes, by simply comparing gene-by-gene functions. Following this approach, Mushegian and Koonin proposed a hypothetical minimal genome, Minimal Gene Set (MGS), aiming for a possible oldest ancestor genome. They obtained MGS by comparing the genomes of two simple bacteria and eliminating duplicated or functionally identical genes. The authors raised the fundamental question of whether a hypothetical organism possessing MGS is able to live or not. We attacked this viability problem specifying in silico the metabolic pathways of the MGS-based prokaryote. We then performed a dynamic simulation of cellular metabolic activities in order to check whether the MGS-prokaryote reaches some equilibrium state and produces the necessary biomass. We assumed these two conditions to be necessary for a living organism. Our simulations clearly show that the MGS does not express an organism that is able to live. We then iteratively proceeded with functional replacements in order to obtain a genome composition that gives rise to equilibrium. We ruled out 76 of the original 254 genes in the MGS, because they resulted in duplication from a functional point of view. We also added seven genes not present in the MGS. These genes encode for enzymes involved in critical nodes of the metabolic network. These modifications led to a genome composed of 187 elements expressing a virtually living organism, Virtual Cell (ViCe), that exhibits homeostatic capabilities and produces biomass. Moreover, the steady-state distribution of the concentrations of virtual metabolites that resulted was similar to that experimentally measured in bacteria. We conclude then that ViCe is able to "live in silico."

A distributed calculus is proposed for describing networks of services. We model service interaction through a call-by-property invocation mechanism, by specifying the security constraints that make their composition safe. A static approach is then proposed to determine how to compose services and guarantee that their execution is always secure, without resorting to any dynamic check.

A static approach is proposed to study secure composition of software. We extend the /spl lambda/-calculus with primitives for invoking services that respect given security requirements. Security-critical code is enclosed in policy framings with a possibly nested, local scope. Policy framings enforce safety and liveness properties of execution histories. The actual histories that can occur at runtime are over-approximated by a type and effect system. These approximations are model-checked to verify policy framings within their scopes. This allows for removing any runtime execution monitor, and for selecting those services that match the security requirements.

We methodically expand protocol narrations into terms of a process algebra in order to specify some of the checks that need to be made in a protocol. We then apply static analysis technology to develop an automatic validation procedure for protocols.

We introduce a Control Flow Analysis that statically approximates the dynamic behaviour of mobile processes, expressed in (a variant of) the π-calculus. Our analysis of a system is able to describe the essential behaviour of each sub-system, tracking

We perform a systematic expansion of protocol narrations into terms of process algebra in order to make precise some of the detailed checks that need to be made in a protocol. We then apply static analysis technology to develop an automatic validation procedure for protocols. Finally, we demonstrate that these techniques suffice for identifying a number of authentication flaws in symmetric key protocols such as Needham-Schroeder, Otway-Rees, Yahalom and Andrew Secure RPC.

We use a structural operational semantics which drives us in inferring quantitative measures on system evolution. The transitions of the system are labeled and we assign rates to them by only looking at these labels. The rates reflect the possibly distributed architecture on which applications run. We then map transition systems to Markov chains, and performance evaluation is carried out using standard tools. As a working example, we compare the performance of a conventional uniprocessor with a prefetch pipeline machine. We also consider two case studies from the literature involving mobile computation to show that our framework is feasible.

We address the problem of message authentication using the /spl pi/-calculus, which has been given an operational semantics that provides each sequential process of a system with its own local space of names. We exploit here that semantics and its localized names to guarantee by construction that a message has been generated by a given entity. Therefore, our proposal can be seen as a reference for the analysis of "real" protocols. As an example, we study the way authentication is ensured by encrypting messages in the spi-calculus.

The random-assignment method for ensuring fairness for non-deterministic and/or concurrent languages is revised in order to make it dependent on the different priorities that each process may have. Priorities affect the choice of the scheduler in that a processes with high priority is preferred to others with a lower priority, still ensuring that all and only fair computations are originated. The actual presentation of the method is based on the non-standard model of the natural numbers of [C70].

Abstract Error recovery techniques for LR parsers presented in the literature are described and classified. The techniques considered range from the non‐correcting ones to interactive and incremental ones. Also, some of the techniques presented are compared and evaluated. An example showing the advantages and the disadvantages of each class of strategies is given and is used as a guideline for classifying syntax errors according to the recovery strategies which are more adequate to correct them.

An algebraic axiomatization is proposed, where, given a net N, a term algebra P(N) with two operations of parallel and sequential composition is defined. The congruence classes generated by a few simple axioms are proved isomorphic to a slight refinement of classical processes. Actually, P(N) is a symmetric monoidal category, parallel composition is the monoidal operation on morphisms and sequential composition is morphism composition. Besides P(N), the authors introduce a category S(N) containing the classical occurrence and step sequences. The term algebras of P(N) and S(N) are in general incomparable, and thus they introduce two more categories, K(N) and T(N), providing a most concrete and a most abstract extremum, respectively. The morphisms of T(N) are proved isomorphic to the processes recently defined in terms of the swap transformation by E. Best and R. Devillers (Theor. Comput. Sci., vol.55, pp.87-136, 1987). Thus the diamond of the four categories gives a full account in algebraic terms of the relations between interleaving and partial ordering observations of place/transition net computations.>

The problem of the relationship between truly concurrent operational and denotational semantics is tackled by mapping syntactic terms on similar semantic domains in both approaches. Occurrence nets are associated to terms through structural operational semantics based on a set of rewriting rules; event structures are defined as denotations for terms, without resorting to categorical constructions. The proof of the equivalence of the two semantics relies on the direct correspondence between occurrence nets and event structures. R. Milner's (1980) calculus of communicating systems is used as a test case; truly concurrent denotional and operational semantics are given for it and proved consistent. This equivalence is established for the first time in true concurrency approach. It is proved that G. Winskel's (1982) categorical denotational semantics is equivalent to that given here.>

A technique for generating parsers which is an extension to LR techniques and is based on parsing table splitting, is presented. Then this technique is slightly extended to support incremental syntax analysis. Given a context-free grammar and a set “ IC ” of nonterminals devised to be incremental, a set of subtables is generated to drive the analysis of program fragments derivable from nonterminals in IC . The proposed technique generates parsing tables which are considerably smaller than the standard ones, even when incrementality is not exploited. Thus, these tables may be stored as arrays permitting faster access and accurate error handling. Furthermore, our tables are suitable for generating syntax-directed editors which provide a full analytic mode. The efficiency of the analytic component of a syntax-directed editor obtained in this way and its easy integration with the generative component stress the advantages of incremental program writing.

In our model, a graph describes a net of processes communicating through ports and, at the same time, its computation history consisting of a partial ordering of events. Stand-alone evolution of processes is specified by context-free productions. From productions and a basic synchronization mechanism, a set of context-sensitive rewriting rules that models the evolution of processes connected to the same ports can be derived. A computation is a sequence of graphs obtained by successive rewritings. The result of a finite computation is its last graph, whereas the result of an infinite computation is the limit, infinite graph defined through a completion technique based on metric spaces. A result characterizes a concurrent computation, since it abstracts from any particular interleaving of concurrent events, while in the meantime providing information about termination, partial or complete deadlocks, and fairness. Not every result is acceptable, however, but only the computations that produce a result no longer rewritable are successful. Infinite successful computations are shown to coincide with weakly fair computations, and a scheduler yielding all and only such computations is defined.

A noninductive method for mechanical theorem proving is presented, which deals with a recursive class of theorems involving iterative functions and predicates. The method is based on the symbolic evaluation of the formula to be proved and requires no inductive step. Induction is avoided since a metatheorem is proved which establishes the conditions on the evaluation of any formula which are sufficient to assure that the formula actually holds. The proof of a supposed theorem consists in evaluating the formula and checking the conditions. The method applies to assertions that involve element-by-element checking of typed homogeneous sequences which are hierarchically constructed out of the primitive type consisting of the truth values. The sequences can be computed by means of iterative and ``accumulator'' functions. The paper includes the definition of a simple typed iterative language in which both predicates and functions are expressed. The language precisely defines the scope of the proof method. The method proves a wide variety of theorems about iterative functions on sequences, including that which states that REVERSE is its own inverse, and that it can be inversely distributed on APPEND, that FLATTEN can be distributed on APPEND and that each element of any sequence is a MEMBER of the sequence itself. Although the method is not complete, it does provide the basis for an extremely efficient tool to be used in a complete mechanical theorem prover.

Four liveness properties of concurrent programs are characterized by the fact that their computations, represented as sequences of partial orderings of events, are convergent in suitable metric spaces. The corresponding topological completions do not therefore contain the infinite computations without the desired properties. The properties are: vitality (i.e. every running process will eventually produce an observable event), global and local fairness, and deadlock freedom. This approach proves fruitful since a universal scheduler is defined, which, when supplied with a particular metric, generates all and only convergent computations. Thus, this scheduler can be used to generate all and only vital, fair or deadlock free computations.