A Set Automaton to Locate All Pattern Matches in a Term

Rick Erkens; Jan Friso Groote

doi:10.48550/arXiv.2106.15311

A Set Automaton to Locate All Pattern Matches in a Term

Rick Erkens, Jan Friso Groote

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic

32 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 [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.

Originele taal-2	Engels
Artikelnummer	2106.15311
Tijdschrift	arXiv
Volume	2021
DOI's	https://doi.org/10.48550/arXiv.2106.15311
Status	Gepubliceerd - 29 jun. 2021

Bibliografische nota

Submitted to ICTAC 2021. Contains appendix with proofs

Toegang tot document

10.48550/arXiv.2106.15311

2106.15311v1Definitieve gepubliceerde versie, 259 KB

Citeer dit

@article{2a503f5d95f24895aee18a77c5067497,

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

keywords = "cs.FL",

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

note = "Submitted to ICTAC 2021. Contains appendix with proofs",

year = "2021",

month = jun,

day = "29",

doi = "10.48550/arXiv.2106.15311",

language = "English",

volume = "2021",

journal = "arXiv",

publisher = "Cornell University Library",

}

TY - JOUR

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

AU - Erkens, Rick

AU - Groote, Jan Friso

N1 - Submitted to ICTAC 2021. Contains appendix with proofs

PY - 2021/6/29

Y1 - 2021/6/29

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

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

KW - cs.FL

U2 - 10.48550/arXiv.2106.15311

DO - 10.48550/arXiv.2106.15311

M3 - Article

VL - 2021

JO - arXiv

JF - arXiv

M1 - 2106.15311

ER -

A Set Automaton to Locate All Pattern Matches in a Term

Samenvatting

Bibliografische nota

Toegang tot document

Vingerafdruk

Citeer dit