Skip Navigation

The Computer Journal 1995 38(5):381-399; doi:10.1093/comjnl/38.5.381
© 1995 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (8)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Eker, S. M.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Associative-commutative matching via bipartite graph matching

S. M. Eker *

INRIA Lorraine, B.P. 101, 54602 Villers-Les-Nancy, France

We consider the problem of term matching where some subset of the function symbols are associative-commutative. Our approach is to build a hierarchy of bipartite graph matching problems which encodes all the possible solutions of subproblems. Sets of solutions to the graph matching problems which are consistent on variable assignments give rise to what we refer to as semi-pure AC systems in which assignments for every variable occurring under a free function symbol in the pattern are known. These semi-pure AC systems are then solved by an exhaustive search to find complete matching substitutions. We give a number of refinements which considerably cut down the search space at all stages in the algorithm leading to efficient solution of non-pathological problem instances.

Received September 16 1993. revised July 7 1995.

* INRIA Lorraine, B.P. 101, 54602 Villers-Les-Nancy, France


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.