Explicit Substitutions à la de Bruijn: the local and global way

Kamareddine and Nederpelt[9], resp. Kamareddine and Ríos [11] gave two calculi of explicit of substitutions highly influenced by de Bruijn's notation of the λ-calculus. These calculi added to the explosive pool of work on explicit substitution in the past 15 years. As far as we know, calculi of explicit substitutions: a) are unable to handle local substitutions, and b) have answered (positively or negatively) the question of the termination of the underlying calculus of substitutions. The exception to a) is the calculus of [9] where substitution is handled both locally and globally. However, the calculus of [9] does not satisfy properties like confluence and termination. The exception to b) is the λs_e-calculus of [11] for which termination of the s_e-calculus, the underlying calculus of substitutions, remains unsolved. This paper has two aims:

(i) To provide a calculus à la de Bruijn which deals with local substitution and whose underlying calculus of substitutions is terminating and confluent.

(ii) To pose the problem of the termination of the substitution calculus of [11] in the hope that it can generate interest as a termination problem which at least for curiosity, needs to be settled. The answer here can go either way. On the one hand, although the λσ-calculus [1] does not preserve termination, the σ-calculus itself terminates. On the other hand, could the non-preservation of termination in the λs_e-calculus imply the non-termination of the s_e-calculus?

Cryptographic Key Agreement for Mobile Radio

Hassan, A. A., Stark, W. E., Hershey, J. E., and Chennakeshu, S., Cryptographic Key Agreement for Mobile Radio,Digital Signal Processing6(1996), 207–212.The problem of establishing a mutually held secret cryptographic key using a radio channel is addressed. The performance of a particular key distribution system is evaluated for a practical mobile radio communications system. The performance measure taken is probabilistic, and different from the Shannon measure of perfect secrecy. In particular, it is shown that by using a channel decoder, the probability of two users establishing a secret key is close to one, while the probability of an adversary generating the same key is close to zero. The number of possible keys is large enough that exhaustive search is impractical.     

Probabilistic π-Calculus and Event Structures

This paper proposes two semantics of a probabilistic variant of the π-calculus: an interleaving semantics in terms of Segala automata and a true concurrent semantics, in terms of probabilistic event structures. The key technical point is a use of types to identify a good class of non-deterministic probabilistic behaviours which can preserve a compositionality of the parallel operator in the event structures and the calculus. We show an operational correspondence between the two semantics. This allows us to prove a “probabilistic confluence” result, which generalises the confluence of the linearly typed π-calculus.     

A Simple Calculus for Proteins and Cells

The use of process calculi to represent biological systems has led to the design of different calculi such as brane calculi [Luca Cardelli. Brane calculi. In CMSB, pages 257–278, 2004] and κ-calculus [Vincent Danos and Cosimo Laneve. Formal molecular biology. Theoritical Computer Science, 325(1):69–110, 2004]. Both have proved to be useful to model different types of biological systems.As an attempt to unify the two directions, we introduce the bioκ-calculus, a simple calculus for describing proteins and cells, in which bonds are represented by means of shared names and interactions are modelled at the domain level. Protein-protein interactions have to be at most binary and cell interactions have to fit with sort constraints.We define the semantics of bioκ-calculus, analyse its properties, and discuss its expressiveness by modelling two significant examples: a signalling pathway and a virus infection.     

Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval

In a recent paper [Theoretical Computer Science 363, 257–265], He, Zhong and Gu considered the non-resumable case of the scheduling problem with a fixed non-availability interval under the non-resumable scenario. They proposed a polynomial time approximation scheme (PTAS) to minimize the total completion time.In this paper, we propose a fully polynomial-time approximation scheme to minimize the total weighted completion time. The FPTAS has O(n²/ε²) time complexity, where n is the number of jobs and ε is the required error bound. The proposed FPTAS outperforms all the previous approximation algorithms designed for this problem and its running time is strongly polynomial.     

A Sequent Calculus for Subtyping Polymorphic Types

We present two complete systems for polymorphic types with sub- typing. One system is in the style of natural deduction, while another is a Gentzen-style sequent calculus system. We prove several meta- mathematical properties for these systems including cut elimination, subject reduction, coherence, and decidability of type reconstruction. Following the approach by J. Mitchell, the sequents are given a simple semantics using logical relations over applicative structures. The systems are complete with respect to this semantics. The logic which emerges from this paper can be seen as a successor to the original Hilbert style system proposed by J. Mitchell in 1988, and to the “half way” sequent calculus of G. Longo, K. Milsted, and S. Soloviev proposed in 1995.     

Probabilistic Logic over Paths

We introduce a probabilistic modal logic PPL extending the work of [Ronald Fagin, Joseph Y. Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Information and Computation, 87(1,2):78–128, 1990; Ronald Fagin and Joseph Y. Halpern. Reasoning about knowledge and probability. Journal of the ACM, 41(2):340–367, 1994] by allowing arbitrary nesting of a path probabilistic operator and we prove its completeness. We prove that our logic is strictly more expressive than other logics such as the logics cited above. By considering a probabilistic extension of CTL we show that this additional expressive power is really needed in some applications.     

A Computationally Sound Mechanized Prover for Security Protocols

We present a new mechanized prover for secrecy properties of security protocols. In contrast to most previous provers, our tool does not rely on the Dolev-Yao model, but on the computational model. It produces proofs presented as sequences of games; these games are formalized in a probabilistic polynomial-time process calculus. Our tool provides a generic method for specifying security properties of the cryptographic primitives, which can handle shared-key and public-key encryption, signatures, message authentication codes, and hash functions. Our tool produces proofs valid for a number of sessions polynomial in the security parameter, in the presence of an active adversary. We have implemented our tool and tested it on a number of examples of protocols from the literature.     

基于概率多项式时间进程的安全协议分析

针对Spi演算在安全协议分析中存在的局限性，通过引入概率多项式时间进程，提出一个分析安全协议的新方法。该方法是对Spi演算的改进，在该方法中攻击者是概率多项式时间进程，协议的安全性用概率可观察等价性表示。通过对一个基于ElGamal加密和Diffie-Hellman的密钥交换协议分析，证明了该方法的可行性和有效性。     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

On the Expressiveness of Chi, Update, and Fusion calculi

Chi and Update calculi [9,17] have been independently introduced in order to model mobile systems. The two calculi are very close to each other and represent an evolution of π-calculus [15]. More recently a (non-straightforward) polyadic version of the Update calculus, the Fusion calculus, has been proposed [18].In the paper we give a fully abstract encoding from an asynchronous variant of Chi and Update calculi to asynchronous π-calculus [11,4]. This proves that, at least for their asynchronous variants, Chi and Update calculi are not more expressive than π-calculus. A similar result can be proved for the Fusion calculus.     

A Novel Stochastic Game Via the Quantitative μ-calculus

The quantitative μ-calculus qMμ extends the applicability of Kozen's standard μ-calculus [D. Kozen, Results on the propositional μ-calculus, Theoretical Computer Science 27 (1983) 333–354] to probabilistic systems. Subsequent to its introduction [C. Morgan, and A. McIver, A probabilistic temporal calculus based on expectations, in: L. Groves and S. Reeves, editors, Proc. Formal Methods Pacific '97 (1997), available at [PSG, Probabilistic Systems Group: Collected reports, http://web.comlab.ox.ac.uk/oucl/research/areas/probs/bibliography.html]; also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap. 9], M. Huth, and M. Kwiatkowska, Quantitative analysis and model checking, in: Proceedings of 12th annual IEEE Symposium on Logic in Computer Science, 1997] it has been developed by us [A. McIver, and C. Morgan, Games, probability and the quantitative μ-calculus qMu, in: Proc. LPAR, LNAI 2514 (2002), pp. 292–310, revised and expanded at [A. McIver, and C. Morgan, Results on the quantitative μ-calculus qMμ (2005), to appear in ACM TOCL]; also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap. 11], A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, A. McIver, and C. Morgan, Results on the quantitative μ-calculus qMμ (2005), to appear in ACM TOCL] and by others [L. de Alfaro, and R. Majumdar, Quantitative solution of omega-regular games, Journal of Computer and System Sciences 68 (2004) 374–397]. Beyond its natural application to define probabilistic temporal logic [C. Morgan, and A. McIver, An expectation-based model for probabilistic temporal logic, Logic Journal of the IGPL 7 (1999), pp. 779–804, also appears at [A. McIver, and C. Morgan, “Abstraction, Refinement and Proof for Probabilistic Systems,” Technical Monographs in Computer Science, Springer, New York, 2005, Chap.10]], there are a number of other areas that benefit from its use.One application is stochastic two-player games, and the contribution of this paper is to depart from the usual notion of “absolute winning conditions” and to introduce a novel game in which players can “draw”.The extension is motivated by examples based on economic games: we propose an extension to qMμ so that they can be specified; we show that the extension can be expressed via a reduction to the original logic; and, via that reduction, we prove that the players can play optimally in the extended game using memoryless strategies.     

Approximation of satisfactory bisection problems

The Satisfactory Bisection problem means to decide whether a given graph has a partition of its vertex set into two parts of the same cardinality such that each vertex has at least as many neighbors in its part as in the other part. A related variant of this problem, called Co-Satisfactory Bisection, requires that each vertex has at most as many neighbors in its part as in the other part. A vertex satisfying the degree constraint above in a partition is called ‘satisfied’ or ‘co-satisfied,’ respectively. After stating the NP-completeness of both problems, we study approximation results in two directions. We prove that maximizing the number of (co-)satisfied vertices in a bisection has no polynomial-time approximation scheme (unless P=NP), whereas constant approximation algorithms can be obtained in polynomial time. Moreover, minimizing the difference of the cardinalities of vertex classes in a bipartition that (co-)satisfies all vertices has no polynomial-time approximation scheme either.     

Types and full abstraction for polyadic π-calculus

A type system for terms of the monadic π-calculus is introduced and used to obtain a full-abstraction result for the translation of the polyadic π-calculus into the monadic calculus: well-sorted terms of the polyadic calculus are barbed congruent iff their translations are typed barbed congruent.     

Expressiveness of Probabilistic π-calculus

In this work we propose a probabilistic extension of the π-calculus. The main novelty is a probabilistic mixed choice operator, that is, a choice construct with a probability distribution on the branches, and where input and output actions can both occur as guards. We develop the operational semantics of this calculus, and then we investigate its expressiveness. In particular, we compare it with the sublanguage with the two separate choices, where input and output guards are not allowed together in the same choice construct. Our main result is that the separate choices can encode the mixed one. Further, we show that input-guarded choice can encode output-guarded choice and viceversa. In contrast, we conjecture that neither of them can encode the pair of the two separate choices.     

Computational complexity of auditing finite attributes in statistical databases

We study the computational complexity of auditing finite attributes in databases allowing statistical queries. Given a database that supports statistical queries, the auditing problem is to check whether an attribute can be completely determined or not from a given set of statistical information. Some restricted cases of this problem have been investigated earlier, e.g. the complexity of statistical sum queries is known by the work of Kleinberg et al. (J. Comput. System Sci. 66 (2003) 244–253). We characterize all classes of statistical queries such that the auditing problem is polynomial-time solvable. We also prove that the problem is coNP-complete in all other cases under a plausible conjecture on the complexity of constraint satisfaction problems (CSP). The characterization is based on the complexity of certain CSP problems; the exact complexity for such problems is known in many cases. This result is obtained by exploiting connections between auditing and constraint satisfaction, and using certain algebraic techniques. We also study a generalization of the auditing problem where one asks if a set of statistical information imply that an attribute is restricted to K or less different values. We characterize all classes of polynomial-time solvable problems in this case, too.     

The reactive simulatability (RSIM) framework for asynchronous systems

We define reactive simulatability for general asynchronous systems. Roughly, simulatability means that a real system implements an ideal system (specification) in a way that preserves security in a general cryptographic sense. Reactive means that the system can interact with its users multiple times, e.g., in many concurrent protocol runs or a multi-round game. In terms of distributed systems, reactive simulatability is a type of refinement that preserves particularly strong properties, in particular confidentiality. A core feature of reactive simulatability is composability, i.e., the real system can be plugged in instead of the ideal system within arbitrary larger systems; this is shown in follow-up papers, and so is the preservation of many classes of individual security properties from the ideal to the real systems.A large part of this paper defines a suitable system model. It is based on probabilistic IO automata (PIOA) with two main new features: One is generic distributed scheduling. Important special cases are realistic adversarial scheduling, procedure-call-type scheduling among colocated system parts, and special schedulers such as for fairness, also in combinations. The other is the definition of the reactive runtime via a realization by Turing machines such that notions like polynomial-time are composable. The simple complexity of the transition functions of the automata is not composable.As specializations of this model we define security-specific concepts, in particular a separation between honest users and adversaries and several trust models.The benefit of IO automata as the main model, instead of only interactive Turing machines as usual in cryptographic multi-party computation, is that many cryptographic systems can be specified with an ideal system consisting of only one simple, deterministic IO automaton without any cryptographic objects, as many follow-up papers show. This enables the use of classic formal methods and automatic proof tools for proving larger distributed protocols and systems that use these cryptographic systems.     

Priority as extremal probability

We extend the stratified model of probabilistic processes to obtain a very general notion ofprocess priority. The main idea is to allow probability guards of value 0 to be associated with alternatives of a probabilistic summation expression. Such alternatives can be chosen only if the non-zero alternatives are precluded by contextual constraints. We refer to this model as one of extremal probability and to its signature asPCCS . We providePCCS with a structural operational semantics and a notionof probabilistic bisimulation, which is shown to be a congruence. Of particular interest is the abstractionPCCS ofPCCS in which all non-zero probability guards are identified.PCCS represents a customized framework for reasoning about priority, and covers all features of process algebras proposed for reasoning about priority that we know of.A preliminary version of this paper appeared inProceedings of CONCUR '90 — First International Conference on Concurrency Theory, Vol. 458 of the Springer-Verlag seriesLecture Notes in Computer Science, pp. 456–466, Aug. 1990. The research of Scott Smolka was supported in part by NSF Grants CCR-9120995, CCR-9208585 and CCR-9505562; and AFOSR Grants F49620-93-1-0250, F49620-95-1-0508 and F49620-96-1-0087.