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 (Corresponderende auteur)
, Jan Friso Groote

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

1 Citaat (Scopus)

15 Downloads (Pure)

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
Subtitel	18th International Colloquium, Virtual Event, Nur-Sultan, Kazakhstan, September 8–10, 2021, Proceedings
Redacteuren	Antonio Cerone, Peter Csaba Olveczky
Uitgeverij	Springer
Pagina's	67-85
Aantal pagina's	19
ISBN van elektronische versie	978-3-030-85315-0
ISBN van geprinte versie	978-3-030-85314-3
DOI's	https://doi.org/10.1007/978-3-030-85315-0_5
Status	Gepubliceerd - 20 aug. 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 (LNCS)
Volume	12819
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Naam	Theoretical Computer Science and General Issues (LNTCS)
Volume	12819
ISSN van geprinte versie	2512-2010
ISSN van elektronische versie	2512-2029

Congres

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

Toegang tot document

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

pdfDefinitieve gepubliceerde versie, 466 KBLicentie: TAVERNE

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, Virtual Event, Nur-Sultan, Kazakhstan, September 8–10, 2021, Proceedings (blz. 67-85). (Lecture Notes in Computer Science (LNCS); Vol. 12819), (Theoretical Computer Science and General Issues (LNTCS); Vol. 12819). 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, Virtual Event, Nur-Sultan, Kazakhstan, September 8–10, 2021, Proceedings. redacteur / Antonio Cerone ; Peter Csaba Olveczky. Springer, 2021. blz. 67-85 (Lecture Notes in Computer Science (LNCS)). (Theoretical Computer Science and General Issues (LNTCS)).

@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\}",

year = "2021",

month = aug,

day = "20",

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

language = "English",

isbn = "978-3-030-85314-3",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "67--85",

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

booktitle = "Theoretical Aspects of Computing – ICTAC 2021",

address = "Germany",

note = "18th International Colloquium on Theoretical Aspects of Computing, ICTAC 2021 ; Conference date: 08-09-2021 Through 10-09-2021",

}

Erkens, R & Groote, JF 2021, A Set Automaton to Locate All Pattern Matches in a Term. in A Cerone & PC Olveczky (reds.), Theoretical Aspects of Computing – ICTAC 2021: 18th International Colloquium, Virtual Event, Nur-Sultan, Kazakhstan, September 8–10, 2021, Proceedings. Lecture Notes in Computer Science (LNCS), vol. 12819, Theoretical Computer Science and General Issues (LNTCS), vol. 12819, 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 (Corresponderende auteur); Groote, Jan Friso.
Theoretical Aspects of Computing – ICTAC 2021: 18th International Colloquium, Virtual Event, Nur-Sultan, Kazakhstan, September 8–10, 2021, Proceedings. reds. / Antonio Cerone; Peter Csaba Olveczky. Springer, 2021. blz. 67-85 (Lecture Notes in Computer Science (LNCS); Vol. 12819), (Theoretical Computer Science and General Issues (LNTCS); Vol. 12819).

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/8/20

Y1 - 2021/8/20

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 - https://www.scopus.com/pages/publications/85115176918

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 - 978-3-030-85314-3

T3 - Lecture Notes in Computer Science (LNCS)

SP - 67

EP - 85

BT - Theoretical Aspects of Computing – ICTAC 2021

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, Virtual Event, Nur-Sultan, Kazakhstan, September 8–10, 2021, Proceedings. Springer. 2021. blz. 67-85. (Lecture Notes in Computer Science (LNCS)). (Theoretical Computer Science and General Issues (LNTCS)). doi: 10.1007/978-3-030-85315-0_5

A Set Automaton to Locate All Pattern Matches in a Term

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit