Catálogo de publicaciones - libros

For narrowing to be an efficient evaluation mechanism, several narrowing strategies have been proposed, although typically for the restricted case of left-linear constructor systems. These assumptions, while reasonable for functional programming applications, are too restrictive for a much broader range of applications to which narrowing can be fruitfully applied, including applications where rules have a non-equational meaning either as in a concurrent system or as in a logical system. In this paper, we propose an efficient lazy narrowing strategy called which can be applied to general term rewriting systems with no restrictions whatsoever. An important consequence of this generalization is the that can now be efficiently supported by narrowing, such as symbolic model checking and theorem proving.

We consider the following problem: Given a term , a rewrite system , a finite set of equations ′ such that is ′-convergent, compute finitely many instances of : ,..., such that, for every substitution , there is an index and a substitution such that (where is the normal form of w.r.t. ).

The goal of this paper is to give equivalent (resp. sufficient) conditions for the finite variant property and to systematically investigate this property for equational theories, which are relevant to security protocols verification. For instance, we prove that the finite variant property holds for Abelian Groups, and a theory of modular exponentiation and does not hold for the theory (Associativity, Commutativity, Unit, Nilpotence, homomorphism).

Cryptographic protocols are small programs which involve a high level of concurrency and which are difficult to analyze by hand. The most successful methods to verify such protocols rely on rewriting techniques and automated deduction in order to implement or mimic the process calculus describing the protocol execution.

We focus on the intruder deduction problem, that is the vulnerability to passive attacks, in presence of several variants of -like axioms (from to Abelian groups, including the theory of ) and homomorphism which are the most frequent axioms arising in cryptographic protocols. Solutions are known for the cases of , of Abelian groups, and of homomorphism alone. In this paper we address the combination of these -like theories with the law of homomorphism which leads to much more complex decision problems.

We prove decidability of the intruder deduction problem in all cases considered. Our decision procedure is in EXPTIME, except for a restricted case in which we have been able to get a PTIME decision procedure using a property of one-counter and pushdown automata.

In order to extend the modeling capabilities of rewriting systems, it is rather natural to consider that the firing of rules can be subject to some probabilistic laws. Considering rewrite rules subject to probabilities leads to numerous questions about the underlying notions and results.

We focus here on the problem of termination of a set of probabilistic rewrite rules. A probabilistic rewrite system is said almost surely terminating if the probability that a derivation leads to a normal form is one. Such a system is said positively almost surely terminating if furthermore the mean length of a derivation is finite. We provide several results and techniques in order to prove positive almost sure termination of a given set of probabilistic rewrite rules. All these techniques subsume classical ones for non-probabilistic systems.

This paper is a contribution to the long standing open problem of uniform termination of Semi-Thue Systems that consist of one rule → . McNaughton previously showed that rules incapable of (1) deleting completely from both sides, (2) deleting completely from the left, and (3) deleting completely from the right, have a decidable uniform termination problem. We use a novel approach to show that Premise (2) or, symmetrically, Premise (3), is inessential. Our approach is based on derivations in which every pair of successive steps has an overlap. We call such derivations single-threaded.

We present a new method for proving termination of term rewriting systems automatically. It is a generalization of the match bound method for string rewriting. To prove that a term rewriting system terminates on a given regular language of terms, we first construct an enriched system over a new signature that simulates the original derivations. The enriched system is an infinite system over an infinite signature, but it is locally terminating: every restriction of the enriched system to a finite signature is terminating. We then construct iteratively a finite tree automaton that accepts the enriched given regular language and is closed under rewriting modulo the enriched system. If this procedure stops, then the enriched system is compact: every enriched derivation involves only a finite signature. Therefore, the original system terminates. We present three methods to construct the enrichment: top heights, roof heights, and match heights. Top and roof heights work for left-linear systems, while match heights give a powerful method for linear systems. For linear systems, the method is strengthened further by a forward closure construction. Using these methods, we give examples for automated termination proofs that cannot be obtained by standard methods.

The first RTA conference took place in Dijon, in 1985. This year, 2005, it takes place in Nara. Nara and Dijon share a glorious past but can be considered as being “Sleeping Beauties”, after the title of a book by the Nobel price novelist yasunari Kawabata.

Is RTA sleeping on its glorious past? Back in the late 80s, many of us feared that this would soon be the case, that research in rewrite systems was deepening the gap with everyday’s computer science practice, and that we should develop rewrite-based powerful provers that would make a difference with the state of art and help address real applications such as software verification.

More than ten years later this has not really happened in the way we thought it would. What has happened is that many research areas, such as programming languages, constraint solving, first-order provers, proof assistants, security theory, and verification have all been fertilized by ideas coming from term rewriting. In return, our field has been renewed by new problems and techniques coming from outside our small community.

I am convinced that this will continue, and that new subject areas will join the journey. There are at least two reasons. To quote a celebrated sentence that I have read in many papers: . This is the first reason: we all like to use equations for modeling problems. The second is that we have developed extremely powerful, sophisticated tools to reason with equations. Many computer scientists do not know these tools. It is our responsibility to preach for their use by showing all we can do with them.

As a window into the subject, we recount some of the history (and geography) of two mature, challenging, partially open, partially closed problems in the theory of rewriting (numbers 13 and 21 from the original ). One problem deals with (criteria for left-linear) confluence and the other with termination (of one linear or string rule), the two paradigmatic properties of interest for rewrite systems of any flavor. Both problems were formulated a relatively long time ago, have seen considerable progress, but remain open. We also venture to contemplate the future evolution and impact of these investigations.

Proof-carrying code provides a mechanism for insuring that a host, or code consumer, can safely run code delivered by a code producer. The host specifies a safety policy as a set of axioms and inference rules. In addition to a compiled program, the code producer delivers a formal proof of safety expressed in terms of those rules that can be easily checked. Foundational proof-carrying code (FPCC) provides increased security and greater flexibility in the construction of proofs of safety. Proofs of safety are constructed from the smallest possible set of axioms and inference rules. For example, typing rules are not included. In our semantic approach to FPCC, we encode a semantics of types from first principles and the typing rules are proved as lemmas. In addition, we start from a semantic definition of machine instructions and safety is defined directly from this semantics. Since FPCC starts from basic axioms and low-level definitions, it is necessary to build up a library of lemmas and definitions so that reasoning about particular programs can be carried out at a higher level, and ideally, also be automated. We describe a high-level organization that involves Hoare-style reasoning about machine code programs. This organization is presented using a detailed example. The example, as well as illustrating the above mentioned approach to organizing proofs, is designed to provide a tutorial introduction to a variety of facets of our FPCC approach. For example, it illustrates how to prove safety of programs that traverse input data structures as well as allocate new ones.

We present a simple term language with explicit operators for erasure, duplication and substitution enjoying a sound and complete correspondence with the intuitionistic fragment of Linear Logic’s Proof Nets. We establish the good operational behaviour of the language by means of some fundamental properties such as confluence, preservation of strong normalisation, strong normalisation of well-typed terms and step by step simulation. This formalism is the first term calculus with explicit substitutions having full composition and preserving strong normalisation.