Search

International audience; We are interested in a natural generalization of term-rewriting techniques to what we call drags, viz. finite, directed, ordered, rooted multigraphs, each vertex of which is labeled by a function symbol. To this end, we develop a rich algebra of drags that generalizes the familiar term algebra and its associated rewriting capabilities. Viewing graphs as terms provides an initial building block for rewriting with such graphs, one that should impact the many areas where computations take place on graphs.

In a previous work (Abstract data type systems, Theoret. Comput. Sci. 173 (2) (1997)), the last two authors presented a combined language made of a (strongly normalizing) algebraic rewrite system and a typed lambda-calculus enriched by pattern-matching definitions following a certain format, called the “General Schema”, which generalizes the usual recursor definitions for natural numbers and similar “basic inductive types”. This combined language was shown to be strongly normalizing. The purpose of this paper is to reformulate and extend the General Schema in order to make it easily extensible, to capture a more general class of inductive types, called “strictly positive”, and to ease the strong normalization proof of the resulting system. This result provides a computation model for the combination of an algebraic specification language based on abstract data types and of a strongly typed functional language with strictly positive inductive types.

International audience; This paper builds on a fundamental notion of rewriting theory that characterizes confluence of a (binary) rewriting relation, Klop's cofinal derivations. Cofinal derivations were used by van Oostrom to obtain another characterization of confluence of a rewriting relation via the existence of decreasing diagrams for all local peaks. In this paper, we show that cofinal derivations can be used to give a new, concise proof of Toyama's celebrated modularity theorem and its recent extensions to rewriting modulo in the case of strongly-coherent systems, an assumption discussed in depth here. This is done by generalizing cofinal derivations to cofinal streams, allowing us in turn to generalize van Oostrom's result to the modulo case.

This paper is part of a long-term effort to increase expressiveness of algebraic specification languages while at the same time having a simple semantic foundation on which efficient execution by rewriting and powerful theorem-proving tools can be based. In particular, our rewriting techniques provide semantic foundations for Maude's functional sublanguage, where they have been efficiently implemented. This effort started in the late 1970s, led by the ADJ group, who promoted equational logic and universal algebra as the semantic basis of program specification languages. An important later milestone was the work around order-sorted algebras and the OBJ family of languages developed at SRI-International in the 1980s. This effort has been substantially advanced in the mid-1990s with the development of Maude, a language based on membership equational logic. Membership equational logic is quite simple, and yet quite powerful. Its atomic formulae are equations and sort membership assertions, and its sentences are Horn clauses. It extends in a conservative way both (a version of) order-sorted equational logic and partial algebra approaches, while Horn logic with equality can be very easily encoded. After introducing the basic concepts of the logic, we give conditions and proof rules with which efficient equational deduction by rewriting can be achieved. We also give completion techniques to transform a specification into one meeting these conditions. We address the important issue of proving that a specification protects a subspecification, a property generalizing the usual notion of sufficient completeness. Using tree-automata techniques, we develop a test-set-based approach for proving inductive theorems about a parameterized specification. We briefly discuss a number of extensions of our techniques, including rewriting modulo axioms such as associativity and commutativity, having extra variables in conditions, and solving goals by narrowing. Finally, we discuss the generality of our approach and how it extends several previous approaches.

This paper extends the termination proof techniques based on rewrite orderings to a higher-order setting, by defining a recursive path ordering for simply typed higher-order terms in η-long β-normal form. This ordering is powerful enough to show termination of several complex examples.

This paper is concerned with the foundations of an extension of pure type systems by abstract data types, hence the name of Abstract Data Type Systems . ADTS generalize inductive types as they are defined in the calculus of constructions, by providing definitions of functions by pattern matching on the one hand, and relations among constructors of the inductive type on the other. It also generalizes the first-order framework of abstract data types by providing function types and higher-order equations. The first half of the paper describes the framework of ADTS, while the second half investigates cases where ADTS are strongly normalizing. This is shown to be the case for the polymorphic lambda calculus (with possibly subtypes) enriched by higher-order algebraic rules obeying a strong generalization of primitive recursion of higher type that we call the general schema . This covers in particular the case of inductive types whose constructors do not have functional arguments. We conjecture that this result holds true for all calculi of the so-called Barendregt's cube. On the other hand, the definition of a schema for the higher-order rules allowing for more general inductive types is left open.

International audience; We extend the termination proof methods based on reduction orderings to higher-order rewriting systems based on higher-order pattern matching. We accommodate, on the one hand, a weakly polymorphic, algebraic extension of Church's simply typed λ-calculus, and on the other hand, any use of eta, as a reduction, as an expansion or as an equation. The user's rules may be of any type in this type system, either a base, functional, or weakly polymorphic type.

Solving equations in the free algebra T ( F, X ) (i.e., unification ) uses the two rules: ƒ( s ) = ƒ( t ) → s = t (decomposition) and s [ x ] = x → ⊥ (occur-check). These two rules are not correct in quotients of T ( F, X ) by a finitely generated congruence = E . Following C. Kirchner, we first define classes of equational theories (called syntactic and cycle-syntactic , respectively) for which it is possible to derive some rules replacing the two above. Then, we show that these abstract classes are relevant: all shallow theories , i.e., theories which can be generated by equations in which variables occur at depth at most one, are both syntactic and cycle syntactic. Moreover, the new set of unification rules is terminating, which proves that unification is decidable and finitary in shallow theories. We give still further extensions. If the set of equivalence classes is infinite, a problem which turns out to be decidable in shallow theories, then shallow theories fulfill Colmerauer′s independence of disequations principle (a conjunction of n disequations is solvable iff each disequation alone is solvable). This allows us to derive quantifier-elimination rules. It turns out that these rules do terminate for shallow theories; hence the first-order theory of the quotient algebra T ( F )/ = E is decidable when F is finite and E is shallow. This extends Mal′cev results on the classes of (permutative) locally-free algebras that are completely axiomatizable.

Rewriting with associativity, commutativity and identity has been an open problem for a long time. In 1989, Baird, Peterson and Wilkerson introduced the notion of constrained rewriting, to avoid the problem of nontermination inherent to the use of identities. We build up on this idea in two ways: by giving a complete set of rules for completion modulo these axioms; by showing how to build appropriate orderings for proving termination of constrained rewriting modulo associativity, commutativity and identity.

obj is a declarative language, with mathematical semantics given by order-sorted equational logic and an operational semantics based on order-sorted term rewriting. obj also has user-definable abstract data types with mixfix syntax and a flexible type system that supports overloading and subtypes. In addition, obj has a powerful generic module mechanism, including nonexecutable “theories” as well as executable “objects”, plus “module expressions” that construct whole subsystems. Design and implementation choices for the obj interpreter are described here in detail.

In a previous work ("Abstract Data Type Systems", TCS 173(2), 1997), the last two authors presented a combined language made of a (strongly normalizing) algebraic rewrite system and a typed lambda-calculus enriched by pattern-matching definitions following a certain format, called the "General Schema", which generalizes the usual recursor definitions for natural numbers and similar "basic inductive types". This combined language was shown to be strongly normalizing. The purpose of this paper is to reformulate and extend the General Schema in order to make it easily extensible, to capture a more general class of inductive types, called "strictly positive", and to ease the strong normalization proof of the resulting system. This result provides a computation model for the combination of an algebraic specification language based on abstract data types and of a strongly typed functional language with strictly positive inductive types., Theoretical Computer Science (2002)

The central idea of constraints is to compute with descriptions of data instead of to compute with data items. Generally speaking, a constraint-based computation mechanism (in a broad sense, this includes for instance deduction calculi and grammar formalisms) can be seen as a two-tired architecture, consisting of A language of data descriptions, and means to compute with data descriptions. Predicate logic is, for reasons that will be explained in this lecture, the natural choice as a framework for expressing data descriptions, that is constraints. A computation formalism which operates on constraints by a well-defined set of operations. The choice of this set of operations typically is a compromise between what is desirable for the computation mechanism, and what is feasible for the constraint system.

We propose two-well founded orderings on multisets that extend the Dershowitz-Manna ordering. Unlike the Dershowitz-Manna ordering, ours do not have a natural monotonicity property. This lack of monotonicity suggests using monotonicity to provide a new characterization of the Dershowitz-Manna ordering. Section 5 proposes an efficient and correct implementation of that ordering.

Inductionless induction consists of using pure equational reasoning for proving the validity of an equation in the initial algebra of a set of equational axioms, which would normally require some kind of induction. Under given hypotheses, the equation is valid iff adding it to the set of axioms does not result in an inconsistency. This inconsistency can be found by the Knuth-Bendix completion algorithm, provided that the signature of the algebra is split into free constructors and defined symbols, which must be completely defined in terms of constructors. This is the base of the so-called inductive completion algorithm of Huet and Hullot. Two key concepts, inductive reducibility and inductive co-reducibility , allow us to extend these techniques in various directions: incomplete specifications, nonfree constructors, no constructors specified, equational term rewriting systems. The method is adapted for proving the consistency property of an enrichment of a specification by new operators and new equations. In addition, we get also a simple algorithm to exhibit a set of constructors of a specification. Finally, inductive co-reducibility is reduced to inductive reducibility and an algorithm for deciding inductive reducibility is given for left linear term rewriting systems.

This work investigates inductive theorem proving techniques for first-order functions whose meaning and domains can be specified by Horn clauses built up from the equality and finitely many unary membership predicates. In contrast with other works in the area, constructors are not assumed to be free. Techniques originating from tree automata are used to describe ground constructor terms in normal form, on which the induction proofs are built up. Validity of (free) constructor clauses is checked by an original technique relying on the recent discovery of a complete axiomatization of finite trees and their rational subsets. Validity of clauses with defined symbols or nonfree constructor terms is reduced to the latter case by appropriate inference rules using a notion of ground reducibility for these symbols. We show how to check this property by generating proof obligations which can be passed over to the inductive prover.

Many of the above ideas arose when discussing with people of the afore mentionned groups (Coq, Demons, Maude, PROTHEO), and especially with Gilles Dowek and Christine Paulin. Mitsuhiro Okada also deserves special thanks for introducing me to the Curry-Howard world, while I was introducing him to its Hurry-Coward counterpart.

We describe an automatic complexity analysis mechanism for programs extracted from proofs carried out with the proof assistant Coq. By extraction, we mean the automatic generation of MiniML code [Pierre Letouzey. Programmation fonctionnelle certifiée – l'extraction de programmes dans l'asistant coq. Technical report, 2004]. By complexity analysis, we mean the automatic generation of a description of the time-complexity of a MiniML program in terms of the number of steps needed for its execution. This description can be a natural number for closed program, that is, programs coming along with their actual inputs. For programs per se, the description is given in terms of a set of recurrence relations which relate the number of steps of a computation in terms of the size of the inputs. Going from these recurrence relation to actual complexity functions is a hard task that requires the use of sophisticated tools for symbolic computations. This part is not implemented for the moment although we have manually used the MAPLE computer algebra system in some cases.

International audience; This paper aims at carrying out termination proofs for simply typed higher-order calculi automatically by using ordering comparisons. To this end, we introduce the computability path ordering (CPO), a recursive relation on terms obtained by lifting a precedence on function symbols. A first version, core CPO, is essentially obtained from the higher-order recursive path ordering (HORPO) by eliminating type checks from some recursive calls and by incorporating the treatment of bound variables as in the so-called computability closure. The well-foundedness proof shows that core CPO captures the essence of computability arguments à la Tait and Girard, therefore explaining its name. We further show that no more type check can be eliminated from its recursive calls without loosing well-foundedness, but one for which we found no counterexample yet. Two extensions of core CPO are then introduced which allow one to consider: the first, higher-order inductive types; the second, a precedence in which some function symbols are smaller than application and abstraction.

http://www.springerlink.com/content/u222753gl333221p/; Abstract canonical systems and inference (ACSI) were introduced to formalize the intuitive notions of good proof and good inference appearing typically in first-order logic or in Knuth-Bendix like completion procedures. Since this abstract framework is intended to be generic, it is of fundamental interest to show its adequacy to represent the main systems of interest. This has been done for ground completion (where all equational axioms are ground) but was still an open question for the general completion process. By showing that the standard completion is an instance of the ACSI framework we close the question. For this purpose, two proof representations, proof terms and proofs by replacement, are compared to built a proof ordering that provides an instantiation adapted to the abstract canonical system framework.