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ößeFormat 
SEKI-SR-88-15_Gramlich-Denzinger_Efficient-AC-Matching-Using-Constraint-Propagation.pdf19,31 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.