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

Rick Erkens, Jan Friso Groote

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

1 Citaat (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings
Redacteuren	Antonio Cerone, Peter Csaba Olveczky
Uitgeverij	Springer
Pagina's	67-85
Aantal pagina's	19
ISBN van geprinte versie	9783030853143
DOI's	https://doi.org/10.1007/978-3-030-85315-0_5
Status	Gepubliceerd - 2021
Evenement	18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021 - Virtual, Online Duur: 8 sep. 2021 → 10 sep. 2021

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12819 LNCS
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021
Stad	Virtual, Online
Periode	8/09/21 → 10/09/21

Bibliografische nota

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Toegang tot document

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

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

Erkens, R., & Groote, J. F. (2021). A Set Automaton to Locate All Pattern Matches in a Term. In A. Cerone, & P. C. Olveczky (editors), Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings (blz. 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. redacteur / Antonio Cerone ; Peter Csaba Olveczky. Springer, 2021. blz. 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 (uitgave), 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, blz. 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. uitgave / Antonio Cerone; Peter Csaba Olveczky. Springer, 2021. blz. 67-85 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12819 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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, redacteurs, Theoretical Aspects of Computing – ICTAC 2021 - 18th International Colloquium, Proceedings. Springer. 2021. blz. 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

Samenvatting

Publicatie series

Congres

Bibliografische nota

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit