A Set Automaton to Locate All Pattern Matches in a Term

Research output: Contribution to journalArticleAcademic

30 Downloads (Pure)

Abstract

Term pattern matching is the problem of finding all pattern matches in a subject term, given a set of patterns. Finding efficient algorithms for this problem is an important direction for research [19]. We present a new 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.
Original languageEnglish
Article number2106.15311
JournalarXiv
Volume2021
DOIs
Publication statusPublished - 29 Jun 2021

Bibliographical note

Submitted to ICTAC 2021. Contains appendix with proofs

Keywords

  • cs.FL

Fingerprint

Dive into the research topics of 'A Set Automaton to Locate All Pattern Matches in a Term'. Together they form a unique fingerprint.

Cite this