Abstract
Unification in many-sorted equational theories is of special interest in automated deduction. It combines the work done on unification in unsorted equational theories and unification in many-sorted signatures without equational theories. The sort structure considered in this paper may be an arbitrary finite partially ordered set, the equational theory may be arbitrary. Combining them, however, requires some natural restrictions, one of which is that equal terms have equal sorts.
Given a unification algorithm A for an unsorted equational theory the corresponding unification algorithm for the many-sorted equational theory is obtained by simply postprocessing the substitutions generated by A with a uniform algorithm to be presented in this paper.
The results obtained concern the decidability of unification as well as the existence and the cardinality of complete and minimal sets of unifiers. The most useful results are obtained for a combination of finitary matching theories with a polymorphic signature.
seismo!mcvax!unido!uklirb!schauss
This work was supported by the Deutsche Forschungsgemeinschaft, SFB 314, “Künstliche Intelligenz”.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Buettner, W., "Unification in the datastructure multiset", Journal of Automated Reasoning, vol.2, pp. 75–88, (1986).
Buettner,W., "Unification in the datastructure set", (to appear in this Proc. of 8th CADE)
Cunningham, R.J., Dick, A.J.J., "Rewrite Systems on a Lattice of Types", Rep. No. DOC 83/7, Imperial College, London SW7 (1983)
Cohn, A.G. "Improving the Expressiveness of Many-sorted Logic.", AAAI-83, Washington (1983)
Fages, F. "Formes canonique dans les algèbres booleènnes et application à la dèmonstration automatique en logique de premier ordre." Thèse du 3eme cycle, Paris, (1983)
Goguen, J.A., Meseguer, J., "Equality, Types, Modules and Generics for Logic Programming", Journal of Logic Programming, (1984)
Goguen, J.A., Meseguer, J., "Order Sorted Algebra I. Partial and Overloaded Operators, Errors and Inheritance.", SRI Report (1985)
Grätzer, G., "Universal algebra", Springer Verlag, (1979)
Hayes, P., "A Logic of Actions.", Machine Intelligence 6, Metamathematics Unit, University of Edinburgh (1971)
Herold, A., "Some basic notions of first order unification theory.", Internal report 15/83, Univ. Karlsruhe, (1983)
Herold, A.,Siekmann, J., "Unification in abelian semigroups", technical report, Universität Kaiserslautern, Memo SEKI-85-III, (1985)
Henschen, L.J., "N-Sorted Logic for Automated Theorem Proving in Higher-Order Logic.", Proc. ACM Conference Boston, (1972)
Huet, G., "Resolution d'equations dans des languages d'ordere 1,2,..., ω;";, These d'Etat, Univ. de Paris, VII, (1976)
Huet, G., Oppen, D.C., "Equations and Rewrite Rules", SRI Technical Report CSL-111, (1980)
Hullot, J.M., "Canonical forms and unification," Proc of the 5 th workshop on automated deduction, Springer Lecture Notes, vol. 87, pp. 318–334, (1980)
Karl Mark G. Raph, "The Markgraf Karl Refutation Procedure", Technical report, Univ. Kaiserslautern, Memo SEKI-84-03, (1984)
Loveland, D., "Automated Theorem Proving", North Holland, (1980)
Livesey,M., Siekmann, J., "Unification of sets and multisets," Technical report, Unive Kaiserslautern, Memo-SEKI-76-01, (1976)
Oberschelp, A., "Untersuchungen zur mehrsortigen Quantorenlogik.", Mathematische Annalen 145 (1962)
Plotkin, G., "Building in equational theories.", Machine Intelligence, vol. 7, 1972
Robinson, J.A., "A Machine-Oriented Logic Based on the Resolution Principle." JACM 12 (1965)
Schmidt-Schauss, M., "A many-sorted calculus with polymorphic functions based on resolution and paramodulation.", Proc 9 th IJCAI, Los Angeles,(1985)
Schmidt-Schauss, M., "Unification in a many-sorted calculus with declarations.", Proc. of GWAI, (1985)
Schmidt-Schauss, M., "Unification in many-sorted equational theories.", Internal report. Institut für Informatik, Kaiserslautern (forthcoming)
Siekmann, J. H., "Universal Unification", Proc. of the 7 th CADE, Napa California, (1984)
Stickel, M.E., "A unification algorithm for Associative-Commutative Functions", JACM 28, pp. 423–434, (1981)
Szabo, P., "Theory of First order Unification.", (in German, thesis) Univ. Karlsruhe, 1982
Walther, C., "A Many-Sorted Calculus Based on Resolution and Paramodulation.", Proc. of the 8 th I JCAI, Karlsruhe, (1983)
Walther, C., "Unification in Many-Sorted Theories.", Proc. of the 6 th ECAI, PISA, (1984)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schmidt-Schauss, M. (1986). Unification in many-sorted equational theories. In: Siekmann, J.H. (eds) 8th International Conference on Automated Deduction. CADE 1986. Lecture Notes in Computer Science, vol 230. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-16780-3_118
Download citation
DOI: https://doi.org/10.1007/3-540-16780-3_118
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16780-8
Online ISBN: 978-3-540-39861-5
eBook Packages: Springer Book Archive