A Set Automaton to Locate All Pattern Matches in a Term

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 [21]. 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
Title of host publicationTheoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings
EditorsAntonio Cerone, Peter Csaba Olveczky
PublisherSpringer
Pages67-85
Number of pages19
ISBN (Print)9783030853143
DOIs
Publication statusPublished - 2021
Event18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021 - Virtual, Online
Duration: 8 Sep 202110 Sep 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12819 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021
CityVirtual, Online
Period8/09/2110/09/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

  • Parallel algorithm
  • Pattern matching
  • Set automaton

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