Abstract
We provide a simple system, based on transformation rules, which is complete for certain classes of semantic matching problems, where the equational theory with respect to which the semantic matching is performed has a convergent rewrite system. We also use this transformation system to describe decision procedures for semantic matching problems. We give counterexamples to show that semantic matching becomes undecidable (as it generally is) when the conditions we give are weakened. Our main result pertains to convergent systems with variable preserving rules, with some particular patterns of defined functions on the right hand sides.
This research was supported in part by the U. S. National Science Foundation under Grants CCR-90-07195 and CCR-90-24271.
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
Alexander Bockmayr. A Note on a Canonical Theory with Undecidable Unification and Matching Problem. In Journal of Automated Reasoning, Vol 3, pages 379–381, 1987.
Nachum Dershowitz and G. Sivakumar. Solving Goals in Equational Languages. In Proceedings of the First International Workshop Conditional Term Rewriting System, Orsay, France, July 1987. Vol. 308, pages 45–55, of Lecture Notes in Computer Science, Springer Verlag (1987).
Nachum Dershowitz and Jean-Pierre Jouannaud. Rewrite systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, chapter 6, pages 243–320, North-Holland, Amsterdam, 1990.
M. Fay. First-order unification in an equational theory. In Proceedings of the Fourth Workshop on Automated Deduction, pages 161–167, Austin, TX, February 1979.
Jean-Marie Hullot. Canonical forms and unification. In R. Kowalski, editor, Proceedings of the Fifth International Conference on Automated Deduction, pages 318–334, Les Arcs, France, July 1980. Vol. 87 of Lecture Notes in Computer Science, Springer, Berlin.
Stephan Heilbrunner and Steffen Holldobler. The Undecidability of the Unification and Matching Problem for Canonical Theories. In Acta Informatica, Vol 24, pages 157–171, 1987.
Jean-Pierre Jouannaud and Claude Kirchner. Solving Equations in Abstract Algebras: A Rule-Based Survey of Unification. In J.-L. Lassez and G. Plotkin, editors, Computational Logic: Essays in Honor of Alan Robinson, MIT Press, Cambridge, MA, 1991.
Deepak Kapur and Paliath Narendran. Matching, Unification and Complexity. In ACM SIGSAM Bulletin, (1987) Vol. 21, Number 4, pages 6–9.
Subrata Mitra. Top-Down Equation Solving and Extensions to Associative and Commutative Theories. Master's thesis, Department of Computer and Information Sciences, University of Delaware, Newark, DE, 1990.
Werner Nutt, Pierre Réty and Gert Smolka. Basic Narrowing Revisited. In J. of Symbolic Computation, (1989) Vol. 7, pages 295–317.
Pierre Réty. Improving basic narrowing techniques. In P. Lescanne, editor, Proceedings of the Second International Conference on Rewriting Techniques and Applications, pages 228–241, Bordeaux, France, May 1987. Vol. 256 of Lecture Notes in Computer Science, Springer, Berlin.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dershowitz, N., Mitra, S., Sivakumar, G. (1992). Decidable matching for convergent systems. In: Kapur, D. (eds) Automated Deduction—CADE-11. CADE 1992. Lecture Notes in Computer Science, vol 607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55602-8_194
Download citation
DOI: https://doi.org/10.1007/3-540-55602-8_194
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55602-2
Online ISBN: 978-3-540-47252-0
eBook Packages: Springer Book Archive