Rick Erkens ; Maurice Laveaux - Adaptive Non-linear Pattern Matching Automata

lmcs:6934 - Logical Methods in Computer Science, December 17, 2021, Volume 17, Issue 4 - https://doi.org/10.46298/lmcs-17(4:21)2021
Adaptive Non-linear Pattern Matching Automata

Authors: Rick Erkens ; Maurice Laveaux

    Efficient pattern matching is fundamental for practical term rewrite engines. By preprocessing the given patterns into a finite deterministic automaton the matching patterns can be decided in a single traversal of the relevant parts of the input term. Most automaton-based techniques are restricted to linear patterns, where each variable occurs at most once, and require an additional post-processing step to check so-called variable consistency. However, we can show that interleaving the variable consistency and pattern matching phases can reduce the number of required steps to find all matches. Therefore, we take the existing adaptive pattern matching automata as introduced by Sekar et al and extend these with consistency checks. We prove that the resulting deterministic pattern matching automaton is correct, and show several examples where some reduction can be achieved.


    Volume: Volume 17, Issue 4
    Published on: December 17, 2021
    Accepted on: October 4, 2021
    Submitted on: November 30, 2020
    Keywords: Computer Science - Logic in Computer Science

    Share

    Consultation statistics

    This page has been seen 185 times.
    This article's PDF has been downloaded 118 times.