Adaptive Non-Linear Pattern Matching Automata

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


    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 a match all matches. Therefore, we take the existing adaptive pattern matching automata as introduced by Sekar et al and extend it these with consistency checks. We prove that the resulting deterministic pattern matching automaton is correct, and show that its evaluation depth is can be shorter than two-phase approaches.
    Originele taal-2Engels
    Titel5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)
    RedacteurenZena M. Ariola
    UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
    Aantal pagina's21
    ISBN van elektronische versie978-3-95977-155-9
    StatusGepubliceerd - 28 jun 2020
    EvenementInternational Conference on Formal Structures for Computation and Deduction - Virtual, Paris, Frankrijk
    Duur: 29 jun 20205 jul 2020

    Publicatie series

    NaamLeibniz International Proceedings in Informatics (LIPIcs)
    ISSN van elektronische versie1868-8969


    CongresInternational Conference on Formal Structures for Computation and Deduction
    Verkorte titelFSCD
    Internet adres

    Vingerafdruk Duik in de onderzoeksthema's van 'Adaptive Non-Linear Pattern Matching Automata'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit