Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-39685
Titel: | Efficient AC-Matching Using Constraint Propagation |
VerfasserIn: | Gramlich, Bernhard Denzinger, Jörg |
Sprache: | Englisch |
Erscheinungsjahr: | 1988 |
Erscheinungsort: | Kaiserslautern |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | We present a new approach to associative-commutative (AC-) pattern matching using a technique of global constraint propagation which in many cases enables us to drastically cut down the search space for solutions. Given a conjunction of simplified non-trivial AC-matching problems the main idea of our method consists in deducing and propagating constraints for possible variable assignments from all problems instead of choosing only one problem for processing next. Thus many failure branches of the search tree for solutions can be cut without expanding them. The control strategy for branching is designed such that nodes with a small branching degree are preferred. Incorporating some additional optimizations we get a new AC-matching algorithm which is especially well-suited for certain non-linear patterns and for a systematic early detection of unsolvability. Moreover we point out the advantages of using unique ordered normal forms for AC-equivalent terms based on a special class of orderings on the function symbols and the variables. Finally we sketch how our constraint propagation approach for AC-matching can be generalized to other kinds of E-matching and E-unification problems. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-396855 hdl:20.500.11880/35826 http://dx.doi.org/10.22028/D291-39685 |
Schriftenreihe: | SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447] |
Band: | 88,15 |
Datum des Eintrags: | 15-Mai-2023 |
Fakultät: | SE - Sonstige Einrichtungen |
Fachrichtung: | SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz |
Professur: | SE - Sonstige |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
SEKI-SR-88-15_Gramlich-Denzinger_Efficient-AC-Matching-Using-Constraint-Propagation.pdf | 19,31 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.