How to realize LSE narrowing

Narrowing is a complete unification procedure for equational theories defined by canonical term rewriting systems. It is also the operational semantics of various logic and functional programming languages. In Ref. 3), we introduced the LSE narrowing strategy, which is complete for arbitrary canonical rewriting systems and optimal in the sense that two different LSE narrowing derivations cannot generate the same narrowing substitution. LSE narrowing improves all previously known strategies for the class of arbitrary canonical systems. LSE narrowing detects redundant derivations by reducibility tests. According to their definition, LSE narrowing steps seem to be very expensive, because a large number of subterms has to be tested. In this paper, we show that many of these subterms are identical. We describe how left-to-right basic occurrences can be used to identify and exclude these identical subterms. This way, we can drastically reduce the number of subterms that have to be tested. Based on these theoretical results, we develop an efficient implementation of LSE narrowing.     

Associative-commutative unification

Unification in equational theories, that is, solving equations in varieties, is of special relevance to automated deduction. Major results in term rewriting systems, as in (Peterson & Stickel, 1981; Hsiang, 1982), depend on unification in presence of associative-commutative functions. (Stickel, 1975; Stickel, 1981) gave an associative-commutative unification algorithm, but its termination in the general case was still questioned.The first part of this paper is an introduction to unification theory, the second part concerns the solving of homogeneous linear diophantine equations, and the third contains a proof of termination and correctness of the associative-commutative unification algorithm for the general case.     

An initial algebra approach to term rewriting systems with variable binders

We present an extension of first-order term rewriting systems. It involves variable binding in the term language. We develop systems called binding term rewriting systems (BTRSs) in a stepwise manner. First we present the term language, then formulate equational logic. Finally, we define rewriting systems. This development is novel because we follow the initial algebra approach in an extended notion of Σ-algebras in various functor categories. These are based on Fiore-Plotkin-Turi’s presheaf semantics of variable binding and Lüth-Ghani’s monadic semantics of term rewriting systems. We characterise the terms, equational logic and rewrite systems for BTRSs as initial algebras in suitable categories. Then, we show an important rewriting property of BTRSs: orthogonal BTRSs are confluent. Moreover, by using the initial algebra semantics, we give a complete characterisation of termination of BTRSs. Finally, we discuss our design choice of BTRSs from a semantic perspective. An erlier version appeared in Proc. Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP2003).     

Equivariant Unification

Nominal logic is a variant of first-order logic with special facilities for reasoning about names and binding based on the underlying concepts of swapping and freshness. It serves as the basis of logic programming, term rewriting, and automated theorem proving techniques that support reasoning about languages with name-binding. These applications often require nominal unification, or equational reasoning and constraint solving in nominal logic. Urban, Pitts and Gabbay developed an algorithm for a broadly applicable class of nominal unification problems. However, because of nominal logic’s equivariance property, these applications also require a different form of unification, which we call equivariant unification. In this article, we first study the complexity of the decision problem for equivariant unification and equivariant matching. We show that these problems are NP-hard in general, as is nominal unification without the ground-name restrictions employed in previous work on nominal unification. Moreover, we present an exponential-time algorithm for equivariant unification that can be used to decide satisfiability, or produce a complete finite set of solutions. We also study special cases that can be solved efficiently. In particular, we present a polynomial time algorithm for swapping-free equivariant matching, that is, for matching problems in which the swapping operation does not appear.     

Sufficient-completeness,ground-reducibility and their complexity

Summary The sufficient-completeness property of equational algebraic specifications has been found useful in providing guidelines for designing abstract data type specifications as well as in proving inductive properties using the induction-less-induction method. The sufficient-completeness property is known to be undecidable in general. In an earlier paper, it was shown to be decidable for constructor-preserving, complete (canonical) term rewriting systems, even when there are relations among constructor symbols. In this paper, the complexity of the sufficient-completeness property is analyzed for different classes of term rewriting systems. A number of results about the complexity of the sufficient-completeness property for complete (canonical) term rewriting systems are proved: (i) The problem is co-NP-complete for term rewriting systems with free constructors (i.e., no relations among constructors are allowed), (ii) the problem remains co-NP-complete for term rewriting systems with unary and nullary constructors, even when there are relations among constructors, (iii) the problem is provably in almost exponential time for left-linear term rewriting systems with relations among constructors, and (iv) for left-linear complete constructor-preserving rewriting systems, the problem can be decided in steps exponential innlogn wheren is the size of the rewriting system. No better lower-bound for the complexity of the sufficient-completeness property for complete (canonical) term rewriting system with nonlinear left-hand sides is known. An algorithm for left-linear complete constructor-preserving rewriting systems is also discussed. Finally, the sufficient-completeness property is shown to be undecidable for non-linear complete term rewriting systems with associative functions. These complexity results also apply to the ground-reducibility property (also called inductive-reducibility) which is known to be directly related to the sufficient-completeness property.Some of the results in this paper were reported in a paper titled Complexity of Sufficient-Completeness presented at theSixth Conf. on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India, Dec. 1986. The term quasi-reducibility is replaced in this paper by ground-reducibility as the latter seems to convey a lot more about the concept than the former.Partially supported by the National Science Foundation Grant nos. CCR-8408461 and CCR-8906678Partially supported by the National Science Foundation Grant nos. CCR-8408461 and CCR-9009414Partially supported by the National Science Foundation Grant no. DCR-8603184     

Inductive proof search modulo

We present an original narrowing-based proof search method for inductive theorems in equational rewrite theories given by a rewrite system $\mathcal{R}$ and a set E of equalities. It has the specificity to be grounded on deduction modulo and to rely on narrowing to provide both induction variables and instantiation schemas. Whenever the equational rewrite system $(\mathcal{R},E)$ has good properties of termination, sufficient completeness, and when E is constructor and variable preserving, narrowing at defined-innermost positions leads to consider only unifiers which are constructor substitutions. This is especially interesting for associative and associative-commutative theories for which the general proof search system is refined. The method is shown to be sound and refutationally correct and complete. A major feature of our approach is to provide a constructive proof in deduction modulo for each successful instance of the proof search procedure.     

Decidability for Left-Linear Growing Term Rewriting Systems

A term rewriting system is called growing if each variable occurring on both the left-hand side and the right-hand side of a rewrite rule occurs at depth zero or one in the left-hand side. Jacquemard showed that the reachability and the sequentiality of linear (i.e., left-right-linear) growing term rewriting systems are decidable. In this paper we show that Jacquemard's result can be extended to left-linear growing rewriting systems that may have right-nonlinear rewrite rules. This implies that the reachability and the joinability of some class of right-linear term rewriting systems are decidable, which improves the results for right-ground term rewriting systems by Oyamaguchi. Our result extends the class of left-linear term rewriting systems having a decidable call-by-need normalizing strategy. Moreover, we prove that the termination property is decidable for almost orthogonal growing term rewriting systems.     

Structures for Abstract Rewriting

When rewriting is used to generate convergent and complete rewrite systems in order to answer the validity problem for some theories, all the rewriting theories rely on a same set of notions, properties, and methods. Rewriting techniques have been used mainly to answer the validity problem of equational theories, that is, to compute congruences. Recently, however, they have been extended in order to be applied to other algebraic structures such as preorders and orders. In this paper, we investigate an abstract form of rewriting, by following the paradigm of logical-system independency. To achieve this purpose, we provide a few simple conditions (or axioms) under which rewriting (and then the set of classical properties and methods) can be modeled, understood, studied, proven, and generalized. This enables us to extend rewriting techniques to other algebraic structures than congruences and preorders such as congruences closed under monotonicity and modus ponens. We introduce convergent rewrite systems that enable one to describe deduction procedures for their corresponding theory, and we propose a Knuth-Bendix–style completion procedure in this abstract framework.     

Unification in Abelian semigroups

Unification in equational theories, i.e., solving of equations in varieties, is a basic operation in computational logic, in artificial intelligence (AI) and in many applications of computer science. In particular the unifiction of terms in the presence of an associative and commutative function, i.e., solving of equations in Abelian semigroups, turned out to be of practical relevance for term rewriting systems, automated theorem provers and many AI-programming languages. The observation that unification under associativity and commutativity reduces to the solution of certain linear diophantine equations is the basis for a complete and minimal unification algorithm. The set of most general unfiers is closely related to the notion of a basis for the linear solution space of these equations.This result is extended to unification in free term algebras combined with Abelian semigroups.     

A Deterministic Lazy Narrowing Calculus

In this paper we study the non-determinism between the inference rules of the lazy narrowing calculusLNC(Middeldorpet al., 1996,Theoret. Comput. Sci.,167, 95–130. We show that all non-determinism can be removed without losing the important completeness property by restricting the underlying term rewriting systems to left-linear confluent constructor systems and interpreting equality as strict equality. For the subclass of orthogonal constructor systems the resulting narrowing calculus is shown to have the nice property that solutions computed by different derivations starting from the same goal are incomparable.     

On sufficient-completeness and related properties of term rewriting systems

Summary The decidability of the sufficient completeness property of equational specifications satisfying certain conditions is shown. In addition, the decidability of the related concept of quasi-reducibility of a term with respect to a set of rules is proved. Other results about irreducible ground terms of a term rewriting system also follow from a key technical lemma used in these decidability proofs; this technical lemma states that there is a finite bound on the substitutions of ground terms that need to be considered in order to check for a given term, whether the result obtained by any substitution of ground terms into the term is irreducible. These results are first shown for untyped systems and are subsequently extended to typed systems.Partially supported by the National Science Foundation Grant no. DCR-8408461     

一种基于模重写系统的攻击者推理方法

为了解决安全协议验证中攻击者模等式理论推理的可操作性问题,提出并设计了一种基于模重写系统的攻击者推理方法。该方法建立在一个反映两种密码原语代数特性的联合理论实例之上,由一组定向的重写规则和非定向的等式构成,前者进一步转化为项重写系统TRS(Term Rewriting System),而后者则转化为有限等价类理论,通过定义项间的模重写关系,使二者构成一个可以反映攻击者针对联合理论代数项操作能力的模重写系统。实例分析表明,该模型为攻击者模等式推理规则赋予了明确的操作语义,可以使攻击者达到对安全协议代数项规约、推理的目的。     

Induction for termination with local strategies

In this paper, we propose a method for specifically proving termination of rewriting with particular strategies: local strategies on operators. An inductive proof procedure is proposed, based on an explicit induction on the termination property. Given a term, the proof principle relies on alternatively applying the induction hypothesis on its subterms, by abstracting the subterms with induction variables, and narrowing the obtained terms in one step, according to the strategy. The induction relation, an F -stable ordering having the subterm property, is not given a priori, but its existence is checked along the proof, by testing satisfiability of ordering constraints.     

A Duality in Proof Systems for Recursive Type Equality and for Bisimulation Equivalence on Cyclic Term Graphs

This paper is concerned with a proof-theoretic observation about two kinds of proof systems for regular cyclic objects. It is presented for the case of two formal systems that are complete with respect to the notion of “recursive type equality” on a restricted class of recursive types in μ-term notation. Here we show the existence of an immediate duality with a geometrical visualization between proofs in a variant of the coinductive axiom system due to Brandt and Henglein and “consistency-unfoldings” in a variant of a 'syntactic-matching' proof system for testing equations between recursive types due to Ariola and Klop.Finally we sketch an analogous result of a duality between a similar pair of proof systems for bisimulation equivalence on equational specifications of cyclic term graphs.     

Proving operational termination of membership equational programs

Reasoning about the termination of equational programs in sophisticated equational languages such as Elan, Maude, OBJ, CafeOBJ, Haskell, and so on, requires support for advanced features such as evaluation strategies, rewriting modulo, use of extra variables in conditions, partiality, and expressive type systems (possibly including polymorphism and higher-order). However, many of those features are, at best, only partially supported by current term rewriting termination tools (for instance mu-term, C i ME, AProVE, TTT, Termptation, etc.) while they may be essential to ensure termination. We present a sequence of theory transformations that can be used to bridge the gap between expressive membership equational programs and such termination tools, and prove the correctness of such transformations. We also discuss a prototype tool performing the transformations on Maude equational programs and sending the resulting transformed theories to some of the aforementioned standard termination tools.     

Lambda Calculus with Explicit Recursion

This paper is concerned with the study ofλ-calculus with explicit recursion, namely of cyclicλ-graphs. The starting point is to treat aλ-graph as a system of recursion equations involvingλ-terms and to manipulate such systems in an unrestricted manner, using equational logic, just as is possible for first-order term rewriting. Surprisingly, now the confluence property breaks down in an essential way. Confluence can be restored by introducing a restraining mechanism on the substitution operation. This leads to a family ofλ-graph calculi, which can be seen as an extension of the family ofλσ-calculi (λ-calculi with explicit substitution). While theλσ-calculi treat the let-construct as a first-class citizen, our calculi support the letrec, a feature that is essential to reason about time and space behavior of functional languages and also about compilation and optimizations of programs     

The unification hierarchy is undecidable

In unification theory, equational theories can be classified according to the existence and cardinality of minimal complete solution sets for equation systems. For unitary, finitary, and infinitary theories minimal complete solution sets always exist and are singletons, finite, or possibly infinite sets, respectively. In nullary theories, minimal complete sets do not exist for some equation systems. These classes form the unification hierarchy.We show that it is not possible to decide where a given equational theory resides in the unification hierarchy. Moreover, it is proved that for some classes this problem is not even recursively enumerable.     

Certifying Term Rewriting Proofs in ELAN

Term rewriting has been shown to be a good environment for both programming and proving. For analysing and debugging rule-based programs, we propose in this work a formalism based on the rewriting calculus with explicit substitutions (ρσ-calculus). This formalism also allows us to build the proof terms of rewriting derivations. Therefore, term rewriting proofs can be exported to other systems by translating them into the corresponding syntaxes. That is, using a proof checker, one can certify these proofs and vice versa, this method allows us to get term rewriting in proof assistants using an external system. Our method not only works with syntactic rewriting but also with rewriting modulo a set of axioms (e.g. associativity-commutativity).     

The undecidability of self-embedding for term rewriting systems

The self-embedding property of term rewriting systems is closely related to the uniform termination property, since a nonself-embedding term rewriting system is uniform terminating. The self-embedding property is shown to be undecidable and partially decidable. It follows that the nonself-embedding property is not partially decidable. This is true even for globally finite term rewriting systems. The same construction gives an easy alternate proof that uniform termination is undecidable in general and also for globally finite term rewriting systems. Also, the looping property is shown to be undecidable in the same way.     

Confluence of Curried Term-Rewriting Systems

Term rewriting systems operate on first-order terms. Presenting such terms in curried form is usually regarded as a trivial change of notation. However, in the absence of a type-discipline, or in the presence of a more powerful type-discipline than simply typed λ-calculus, the change is not as trivial as one might first think.It is shown that currying preserves confluence of arbitrary term rewriting systems. The structure of the proof is similar to Toyama's proof that confluence is a modular property of TRS.