Download A proof theory for general unification by W. Snyder PDF

By W. Snyder

During this monograph we examine generalizations of ordinary unification, E-unification and higher-order unification, utilizing an summary method orig­ inated by means of Herbrand and constructed on the subject of typical first-order unifi­ cation by way of Martelli and Montanari. The formalism offers the unification computation as a suite of non-deterministic transformation principles for con­ verting a collection of equations to be unified into an specific illustration of a unifier (if such exists). this gives an summary and mathematically stylish technique of analysing the houses of unification in quite a few settings via offering a fresh separation of the logical concerns from the specification of procedural details, and quantities to a collection of 'inference ideas' for unification, therefore the identify of this booklet. We derive the set of ameliorations for common E-unification and better­ order unification from an research of the feel during which phrases are 'the similar' after software of a unifying substitution. In either circumstances, this ends up in an easy extension of the set of easy changes given via Herbrand­ Martelli-Montanari for traditional unification, and indicates basically the fundamental relationships of the elemental operations priceless in every one case, and therefore the underlying constitution of an important periods of time period unifi­ cation difficulties.

Show description

Read Online or Download A proof theory for general unification PDF

Best history & philosophy books

A Summary of Scientific Method

A precis of medical process is a short description of what makes technology medical. it really is written in a right away, transparent variety that's available and informative for scientists and technological know-how scholars. it really is meant to assist technology lecturers clarify how technological know-how works, highlighting strengths with out ignoring obstacles, and to aid scientists articulate the method and criteria in their paintings.

Technology's Storytellers: Reweaving the Human Fabric

Technology's Storytellers files the emergence of the background of know-how as a coherent highbrow self-discipline. according to an research of approximately three hundred articles released in know-how and tradition, it proposes a style of old learn as a communal instead of an individualistic activity -- trying to find styles of consensus within the authors' number of time classes, geographical destinations, and kinds of know-how to check.

Low Power Design Methodologies

Low strength layout Methodologies offers the 1st in-depth assurance of the entire layers of the layout hierarchy, starting from the know-how, circuit, good judgment and architectural degrees, as much as the method layer. The e-book provides perception into the mechanisms of energy dissipation in electronic circuits and provides state-of-the-art techniques to strength relief.

Effective Theories in Physics: From Planetary Orbits to Elementary Particle Masses

There's major curiosity within the Philosophy of technology group to appreciate the position that "effective theories" have within the paintings of leading edge technology. the guidelines of powerful theories were implicit in technological know-how for a very long time, yet have simply been articulated good within the previous few a long time. considering that Wilson's renormalization workforce revolution within the early 1970's, the technological know-how group has come to extra totally comprehend its energy, and through the mid-1990's it had won its apotheosis.

Additional resources for A proof theory for general unification

Sample text

E E, and O(Ui) = O(Vi) for 1 $ i $ n; or (iii) u is a variable not in V ar( v) or vice versa. If u is a variable and u f/. V ar( v), then [vlu] E U(u, v) and [vlu] $ O. By extending this analysis to account for systems of equations, we have a set of transformations for finding mgu's. 5 (The set of transformation rules ST) Let S denote any system (possibly empty), ! E E, and u and v be two terms. We have the following transformations. Trivial: {u~u}uS ~ (1) S Term Decomposition: For any ! E En for some n > 0, Variable Elimination: {z~v}US ~ {z~v}Uq(S), where z ~ v is not in solved form, x f/.

The problems which arise with global variables in functional programming languages. Clearly if -< is a partial order, then this holds for any two elements of A, distinct or not. 5 35 TERM REWRITING from left to right, we are usually interested in the reduction relation --and the fact that there are no infinite sequences ao, ... , an, a n+l, . such that an --- an+l for all n ~ O. Thus, following other authors, including Dershowitz, we adopt the dual of the standard set theoretic definition. For the same reason, in the next two definitions we use posets of the form (A, >-) rather than of the form (A, -<).

Note that from our previous definitions, for any two terms u and v and set of equations E, we have u ~E v iff there exists some sequence of equality steps for n ~ 0, where the sequence of equations Ii == ri consists of variants of equations from E U E- l . , for a given E and two terms u and v, whether u ~E v, is called the word problem for E. That this is not a decidable problem is shown by our next result. 4 The relation ~E is in general only semi-decidable. Proof It should be obvious that it is decidable whether a given sequence of rewrite steps proves that u ~E v, and by the previous results, if u ~E v for some set E, then there must exist a finite equational proof of this fact.

Download PDF sample

Rated 4.10 of 5 – based on 49 votes