2021/08/23 by Andrei P. Nemytykh, Nemytykh, Andrei P.
Computer Science · #Algorithms and Data Compression #D.2.4 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #I.1.3 #Logic in Computer Science (cs.LO) #Natural Language Processing Techniques #Programming Languages (cs.PL) #Software Engineering (cs.SE) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2108.10865
openalex publication_date 2021/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We have proved that for any pattern p the tail recursive program model of naive pattern matching may be automatically specialized w.r.t. the pattern p to a specialized version of the so-called KMP-algorithm, using the Higman-Kruskal relation that controls the unfolding/folding. Given an input string, the corresponding residual program finds the first occurrence of p in the string in linear time on the string length. The current state of the automated program specialization art based on unfolding/folding is too weak in order to be able to reproduce the proof, done by hands, of the uniform property above, while it known before that program specialization is sometimes able to produce the KMP-algorithm for a few concrete static patterns.