Rick Erkens: A Set Automaton to Locate All Pattern Matches in a Term

Event Details

Term pattern matching is the problem of finding all pattern matches in a subject term, given a set of patterns. It is a fundamental algorithmic problem in for instance automated theorem proving and term rewriting. We present a set automaton solution for the term pattern matching problem that is based on match set derivatives where each function symbol in the subject pattern is visited exactly once. The algorithm allows for various traversal patterns over the subject term and is particularly suited to search the subject term in parallel using a large number of simultaneously running threads.

This is joint work with Jan Friso Groote.