DocumentCode :
2717191
Title :
Syntactic theories and unification
Author :
Kirchner, Claude ; Klay, Francis
Author_Institution :
INRIA Lorraine, Vandoeuvre-les-Nancy, France
fYear :
1990
fDate :
4-7 Jun 1990
Firstpage :
270
Lastpage :
277
Abstract :
An investigation is made of the relationship between unifiability of a general equation of the form f1, . . ., νn)=?gn+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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
DOI :
10.1109/LICS.1990.113753
Filename :
113753
Link To Document :
بازگشت