Abstract
This paper presents a sound and complete set of abstract transformation rules for rigid E-unification. Abstract congruence closure, syntactic unification and paramodulation are the three main components of the proposed method. The method obviates the need for using any complicated term orderings and easily incorporates suitable optimization rules. Characterization of substitutions as congruences allows for a comparatively simple proof of completeness using proof transformations. When specialized to syntactic unification, we obtain a set of abstract transition rules that describe a class of efficient syntactic unification algorithms.
The research described in this paper was supported in part by the National Science Foundation under grant CCR-9902031.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)
Bachmair, L., Ramakrishnan, C., Ramakrishnan, I.V., Tiwari, A.: Normalization via rewrite closures. In: Narendran, P., Rusinowitch, M. (eds.) RTA 1999. LNCS, vol. 1631, pp. 190–204. Springer, Heidelberg (1999)
Bachmair, L., Ramakrishnan, I.V., Tiwari, A., Vigneron, L.: Congruence closure modulo associativity and commutativity. In: Kirchner, H. (ed.) FroCos 2000. LNCS(LNAI), vol. 1794, pp. 245–259. Springer, Heidelberg (2000)
Bachmair, L., Tiwari, A.: Abstract congruence closure and specializations. In: McAllester, D. (ed.) 17th Intl Conf on Automated Deduction (2000)
Becher, G., Petermann, U.: Rigid unification by completion and rigid paramodulation. In: Dreschler-Fischer, L., Nebel, B. (eds.) KI 1994. LNCS(LNAI), vol. 861, pp. 319–330. Springer, Heidelberg (1994)
Beckert, B.: A completion-based method for mixed universal and rigid E- unification. In: Bundy, A. (ed.) CADE 1994. LNCS(LNAI), vol. 814, pp. 678–692. Springer, Heidelberg (1994)
Degtyarev, A., Voronkov, A.: The undecidability of simultaneous rigid E- unification. Theoretical Computer Science 166(1-2), 291–300 (1996)
Degtyarev, A., Voronkov, A.: What you always wanted to know about rigid E-unification. Journal of Automated Reasoning 20(1), 47–80 (1998)
Gallier, J., Narendran, P., Plaisted, D., Snyder, W.: Rigid E-unification: Np- completeness and applications to equational matings. Information and Computation 87, 129–195 (1990)
Gallier, J., Narendran, P., Raatz, S., Snyder, W.: Theorem proving using equational matings and rigid E-unification. Journal of the Association for Computing Machinery 39(2), 377–429 (1992)
Goubault, J.: A rule-based algorithm for rigid E-unification. In: Mundici, D., Gottlob, G., Leitsch, A. (eds.) KGC 1993. LNCS, vol. 713, pp. 202–210. Springer, Heidelberg (1993)
Kapur, D.: Shostak’s congruence closure as completion. In: Comon, H. (ed.) RTA 1997. LNCS, vol. 1232, pp. 23–37. Springer, Heidelberg (1997)
de Kogel, E.: Rigid E-unification simplified. In: Baumgartner, P., Posegga, J., Hähnle, R. (eds.) TABLEAUX 1995. LNCS(LNAI), vol. 918, pp. 17–30. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tiwari, A., Bachmair, L., Ruess, H. (2000). Rigid E-Unification Revisited. In: McAllester, D. (eds) Automated Deduction - CADE-17. CADE 2000. Lecture Notes in Computer Science(), vol 1831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10721959_17
Download citation
DOI: https://doi.org/10.1007/10721959_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67664-5
Online ISBN: 978-3-540-45101-3
eBook Packages: Springer Book Archive