Title :
Syntactic theories and unification
Author :
Kirchner, Claude ; Klay, Francis
Author_Institution :
INRIA Lorraine, Vandoeuvre-les-Nancy, France
Abstract :
An investigation is made of the relationship between unifiability of a general equation of the form f(ν1, . . ., νn)=?g(νn+1, . . ., ν m), and of the syntacticness of the theory. After introducing the concept of general equations and its basic properties, the precise definition of syntactic theories is given. It is proven that a theory is syntactic if and only is the general equations have finite complete set of E-solutions. The result is constructive in the sense that from the E-solutions of the general equations, a resolvent presentation is computed. This is applied to several theories: in particular, in order to show that distributivity is not syntactic. The authors also prove that the theory of associativity and commutativity is syntactic, which allows one, by the combination of Nipkow´s results (ibid., p.278-88, 1990) and the authors´, to infer a novel matching algorithm where there is no need to solve linear diophantine equations
Keywords :
decidability; formal logic; E-solutions; associativity; commutativity; distributivity; finite complete set; matching algorithm; resolvent presentation; syntactic theories; unifiability; Abstract algebra; Equations; Heart; Inference algorithms; Logic programming; Mathematics; Sufficient conditions; Vents;
Conference_Titel :
Logic in Computer Science, 1990. LICS '90, Proceedings., Fifth Annual IEEE Symposium on e
Conference_Location :
Philadelphia, PA
Print_ISBN :
0-8186-2073-0
DOI :
10.1109/LICS.1990.113753