Abstract
We present an approach to prove several theorems in slightly different axiom systems simultaneously. We represent the different problems as a taxonomy, i.e. a tree in which each node inherits all knowledge of its predecessors, and solve the problems using inference steps on rules and equations with simple constraints, i.e. words identifying nodes in the taxonomy. We demonstrate that a substantial gain can be achieved by using taxonomic constraints, not only by avoiding the repetition of inference steps but also by achieving run times that are much shorter than the accumulated run times when proving each problem separately.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Avenhaus, J.; Denzinger, J.: Distributing equational theorem proving, Proc. 5th RTA, Montreal, LNCS 690, 1993, pp. 62–76.
Avenhaus, J.; Denzinger, J.; Fuchs, M.: DISCOUNT: A system for distributed equational deduction, Proc. 6th RTA, Kaiserslautern, LNCS 914, 1995, pp. 397–402.
Bachmair, L.; Dershowitz, N.; Plaisted, D.A.: Completion without Failure, Coll. on the Resolution of Equations in Algebraic Structures, Austin (1987), Academic Press, 1989.
Brachman, R.J.; Schmolze, J.G.: On Overview of the KL-ONE Knowledge Representation System, Cognitive Science 9(2), 1985, pp. 171–216.
Bürckert, H.-J.: A Resolution Principle for Clauses with Constraints, Proc. 10th CADE, Kaiserslautern, Springer, LNAI 449, 1990, pp. 178–192.
Dahn, B.I.; Gehne, J.; Honigmann, T.; Walther, L.; Wolf, A.: Integrating Logical Functions with ILF, Internal report, Humbold-University, Berlin, 1994.
Denzinger, J.: Completion and Equational Theorem Proving using Taxonomic Constraints, SEKI-Report SR-95-11, University of Kaiserslautern, 1995.
Denzinger, J.; Fuchs, M.: Goal oriented equational theorem proving using teamwork, Proc. 18th KI-94, Saarbrücken, LNAI 861, 1994, pp. 343–354.
Dershowitz, N.; Jouannaud, J.P.: Rewriting systems, in J. van Leeuwen (Ed.): Handbook of theoretical computer science, Vol. B., Elsevier, 1990, pp. 241–320.
Hsiang, J.; Rusinowitch, M.: On word problems in equational theories, Proc. 14th ICALP, Karlsruhe, LNCS 267, 1987, pp. 54–71.
Huet, G.: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems, Journal of ACM, Vol. 27, No. 4, 1980, pp. 798–821.
Knuth, D.E.; Bendix, P.B.: Simple Word Problems in Universal Algebra, Computational Algebra, J. Leech, Pergamon Press, 1970, pp. 263–297.
Kokorin, A.I.; Kopytov, V.M.: Fully ordered groups, Halsted Press, 1974.
Kurihara, M.; Kondo, H.; Ohuchi, A.: Completion for Multiple Reduction Orderings, Proc. 6th RTA, Kaiserslautern, LNCS 914, 1995, pp. 71–85.
Kirchner, C.; Kirchner, H.; Rusinowitch, M.: Deduction with symbolic constraints, Revue d'Intelligence Artificielle 4(3), 1990, pp. 9–52.
Kleinknecht, R.; Wüst, E.: Lehrbuch der elementaren Logik, Bd. 1: Aussagenlogik, DTV-Verlag, 1976.
Tarski, A.: Logic, Semantics, Metamathematics, Oxford University Press, 1956.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Denzinger, J. (1996). Equational theorem proving using taxonomic constraints. In: Görz, G., Hölldobler, S. (eds) KI-96: Advances in Artificial Intelligence. KI 1996. Lecture Notes in Computer Science, vol 1137. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61708-6_44
Download citation
DOI: https://doi.org/10.1007/3-540-61708-6_44
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61708-2
Online ISBN: 978-3-540-70669-4
eBook Packages: Springer Book Archive