Title: Mergeable schedules for lazy matching
Authors: De Koninck, Leslie
Issue Date: Dec-2007
Publisher: Department of Computer Science, K.U.Leuven
Series Title: CW Reports vol:CW505
Abstract: This paper presents a new data structure, based on circular linked lists and the union-find algorithm, for the purpose of incremental, lazy pattern matching for rule based languages, with storage of partial matches. Our approach consists of incrementally generating a schedule of matches. It extends previous work in that it allows merging of such schedules without increasing the overall complexity. Schedule merges are needed in the context of non-ground data. Therefore, our mergeable schedules can be used to implement matching for the Constraint Handling Rules (CHR) language. Our technique forms an alternative to the matching algorithm that is most commonly used by current CHR implementations and which does not keep track of partial matches, but does keep a history of rule firings.
Publication status: published
KU Leuven publication type: IR
Appears in Collections:Informatics Section

Files in This Item:
File Description Status SizeFormat
CW505.pdfDocument Published 358KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.