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

By W. Snyder

During this monograph we examine generalizations of normal unification, E-unification and higher-order unification, utilizing an summary technique orig­ inated by way of Herbrand and constructed on the subject of normal 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 particular illustration of a unifier (if such exists). this gives an summary and mathematically based technique of analysing the houses of unification in quite a few settings via delivering a fresh separation of the logical concerns from the specification of procedural details, and quantities to a collection of 'inference principles' for unification, for this reason the name of this publication. We derive the set of modifications for common E-unification and better­ order unification from an research of the experience during which phrases are 'the similar' after program of a unifying substitution. In either circumstances, this leads to an easy extension of the set of uncomplicated changes given through Herbrand­ Martelli-Montanari for normal unification, and exhibits basically the fundamental relationships of the basic operations worthwhile in every one case, and therefore the underlying constitution of crucial periods of time period unifi­ cation difficulties.

Show description

Read Online or Download A proof theory for general unification PDF

Similar history & philosophy books

Philosophy of Language and the Challenge to Scientific Realism

During this e-book Christopher Norris develops the case for clinical realism by means of tackling a number of adversary arguments from a number anti-realist positions. via an in depth severe examining he exhibits how they fail to make enough experience on any rational, constant and scientifically trained survey of the facts.

Nietzsche, biology, and metaphor

This examine explores the German philosopher's reaction to the highbrow debates sparked by way of the e-book of Charles Darwin's beginning of Species. via reading the abundance of organic metaphors in Nietzsche's writings, Gregory Moore questions his contemporary recognition as an eminently subversive and submit sleek philosopher.

Simplicius : on Aristotle physics 1.5-9

Simplicius' maximum contribution in his statement on Aristotle on Physics 1. 5-9 lies in his remedy of subject. this is often its first translation into English. The sixth-century thinker begins with a helpful elucidation of what Aristotle ability by means of 'principle' and 'element' in Physics. Simplicius' personal belief of subject is of a volume that's totally diffuse as a result of its severe distance from its resource, the Neoplatonic One, and he attempts to discover this belief either in Plato's account of house and in a stray comment of Aristotle's.

Extra info for A proof theory for general unification

Example text

2. It is easy to show that for any poset (S, >-) we have associated posets (M, ~) (where M is the set of all finite multisets of members of S) and (BB, >-'ez) for n > O. Furthermore >- is total (respectively, well-founded) iff >-'ez (for any n) is total (respectively, well-founded) iff ~ is total (respectively, well-founded). We are interested of course in using orderings on terms to prove termination of rewrite systems, and, more generally, to do inductive proofs. The most general of these orderings are based on the notion of syntactic simplification.

3 Let E ~ T~(X) x T~(X) be a set of equations. We define the relation - E over T~(X) as the smallest symmetric, stable, and monotonic relation that contains E. This relation is defined explicitly E t2 iff as follows: Given any two terms t1, t2 E TI;(X), we have t1 there is some variant 5 s == t of an equation in E U E- 1 , some tree address a in t1, and some substitution u, such that tda = u(s), and t2 =tdo +- u(t)]. (Thus, u is a matching substitution of s onto t t! ) Note that the equation s ~ t is used as a two-way rewrite rule (that is, non-oriented).

But the variant assumption for the use of rules allows us to sharpen this test so that we may confine our search for critical overlaps to an examination of the rules themselves. :... :... r2 are two variants of (not necessarily distinct) rewrite rules. Then there exists a critical overlap of the two rules on t iff there exists a substitution u = mgu(ldf3, 12), where ~ E NonVarDom(h). = u(ld. For the other direction, since f3 E NonVarDom(ld, we have t/Otf3 = Pl(h)/f3 = Proof. The if part of the proof is trivial, by taking t Pl(ldf3) = P2(l2).

Download PDF sample

Rated 4.53 of 5 – based on 41 votes