2026/06/25 by Martin Berglund, Brink van der Merwe, Iain le Roux · 1 voice
Computer Science · #Asynchronous communication #Automaton #Backtracking #Computation #Look-ahead #Machine Learning and Algorithms #Matching (statistics) #Memoization #Network Packet Processing and Optimization #Reachability #Set (abstract data type) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.4204/eptcs.446.1
openalex publication_date 2026/06/25 · arxiv published 2026/06/25 · arxiv updated 2026/06/25 · openalex created_date 2026/06/28 · openalex updated_date 2026/08/01
Backtracking regular expression matchers are widely used due to their expressive power but may exhibit exponential worst-case matching time. Memoization provides a principled method for eliminating redundant computation and ensuring linear matching time, but full memoization is memory-intensive and impractical. We introduce the Minimum Feedback Node (MFN) memoization scheme, a selective memoization strategy based on computing a minimum feedback vertex set of an automaton. We establish relationships with existing memoization schemes and analyze their behaviour under both Thompson and Glushkov automaton constructions.