A Set Automaton to Locate All Pattern Matches in a Term

Rick Erkens; Jan Friso Groote

doi:10.1007/978-3-030-85315-0_5

A Set Automaton to Locate All Pattern Matches in a Term

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings
Editors	Antonio Cerone, Peter Csaba Olveczky
Publisher	Springer
Pages	67-85
Number of pages	19
ISBN (Print)	9783030853143
DOIs	https://doi.org/10.1007/978-3-030-85315-0_5
Publication status	Published - 2021
Event	18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021 - Virtual, Online Duration: 8 Sept 2021 → 10 Sept 2021

Publication series

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

Conference

Conference	18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021
City	Virtual, Online
Period	8/09/21 → 10/09/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

Parallel algorithm
Pattern matching
Set automaton

Access to Document

10.1007/978-3-030-85315-0_5

Cite this

Erkens, R., & Groote, J. F. (2021). A Set Automaton to Locate All Pattern Matches in a Term. In A. Cerone, & P. C. Olveczky (Eds.), Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings (pp. 67-85). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12819 LNCS). Springer. https://doi.org/10.1007/978-3-030-85315-0_5

Erkens, Rick ; Groote, Jan Friso. / A Set Automaton to Locate All Pattern Matches in a Term. Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings. editor / Antonio Cerone ; Peter Csaba Olveczky. Springer, 2021. pp. 67-85 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0e6605167c97488f86f24da29f797373,

title = "A Set Automaton to Locate All Pattern Matches in a Term",

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.",

keywords = "Parallel algorithm, Pattern matching, Set automaton",

author = "Rick Erkens and Groote, {Jan Friso}",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021 ; Conference date: 08-09-2021 Through 10-09-2021",

year = "2021",

doi = "10.1007/978-3-030-85315-0_5",

language = "English",

isbn = "9783030853143",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "67--85",

editor = "Antonio Cerone and Olveczky, {Peter Csaba}",

booktitle = "Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings",

address = "Germany",

}

Erkens, R & Groote, JF 2021, A Set Automaton to Locate All Pattern Matches in a Term. in A Cerone & PC Olveczky (eds), Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12819 LNCS, Springer, pp. 67-85, 18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021, Virtual, Online, 8/09/21. https://doi.org/10.1007/978-3-030-85315-0_5

A Set Automaton to Locate All Pattern Matches in a Term. / Erkens, Rick ; Groote, Jan Friso.

Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings. ed. / Antonio Cerone; Peter Csaba Olveczky. Springer, 2021. p. 67-85 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12819 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A Set Automaton to Locate All Pattern Matches in a Term

AU - Erkens, Rick

AU - Groote, Jan Friso

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Parallel algorithm

KW - Pattern matching

KW - Set automaton

UR - http://www.scopus.com/inward/record.url?scp=85115176918&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-85315-0_5

DO - 10.1007/978-3-030-85315-0_5

M3 - Conference contribution

AN - SCOPUS:85115176918

SN - 9783030853143

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 67

EP - 85

BT - Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings

A2 - Cerone, Antonio

A2 - Olveczky, Peter Csaba

PB - Springer

T2 - 18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021

Y2 - 8 September 2021 through 10 September 2021

ER -

Erkens R , Groote JF. A Set Automaton to Locate All Pattern Matches in a Term. In Cerone A, Olveczky PC, editors, Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings. Springer. 2021. p. 67-85. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-85315-0_5

A Set Automaton to Locate All Pattern Matches in a Term

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this