A faster algorithm for finding shortest substring matches of a regular expression

DOI10.1016/j.ipl.2018.12.001zbMath1478.68463OpenAlexW2903931520MaRDI QIDQ1711433

Hiroaki Yamamoto

Publication date: 18 January 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.12.001

zbMATH Keywords

design of algorithmsfinite automatonmatching algorithmregular expressionshortest substring

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Formal languages and automata (68Q45) Algorithms on strings (68W32)

Cites Work

• A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
• Approximate matching of regular expressions
• Regular expressions into finite automata
• Follow automata.
• New techniques for regular expression searching
• Prefix-free regular languages and pattern matching
• New Algorithms for Regular Expression Matching
• A Four Russians algorithm for regular expression pattern matching
• Programming Techniques: Regular expression search algorithm
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A faster algorithm for finding shortest substring matches of a regular expression