Faster Regular Expression Matching

DOI10.1007/978-3-642-02927-1_16MaRDI QIDQ3638033zbMATH OpenOpenAlexFDO

Authors Philip Bille, Mikkel Thorup

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02927-1_16

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Fast and compact regular expression matching
• New Algorithms for Regular Expression Matching
• scientific article; zbMATH DE number 1962812
• A Four Russians algorithm for regular expression pattern matching
• New techniques for regular expression searching

Cited in

(31)

• Fast pattern matching in indexed texts
• On the size of partial derivatives and the word membership problem
• From regular expression matching to parsing
• Dictionary matching with a few gaps
• Fast and compact regular expression matching
• NR-grep: A fast and flexible pattern-matching tool
• Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA
• Optimally streaming greedy regular expression parsing
• New Algorithms for Regular Expression Matching
• scientific article; zbMATH DE number 140453 (Why is no real title available?)
• scientific article; zbMATH DE number 1962812 (Why is no real title available?)
• String matching with variable length gaps
• Efficient Submatch Extraction for Practical Regular Expressions
• Tighter connections between Formula-SAT and shaving logs
• Negative factor. Improving regular-expression matching in strings
• From Regular Expression Matching to Parsing
• Dynamic behavior matching: a complexity analysis and new approximation algorithms
• Two-pass greedy regular expression parsing
• Fast searching in packed strings
• Space-efficient representations for Glushkov automata
• String Processing and Information Retrieval
• An improved prefix-free regular-expression matching
• Regular expression matching with multi-strings and intervals
• Combinatorial Pattern Matching
• scientific article; zbMATH DE number 7651219 (Why is no real title available?)
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• Co-lexicographically ordering automata and regular languages. I
• Text indexing for simple regular expressions
• Efficient matching of some fundamental regular expressions with backreferences
• Compact representations of automata for regular expression matching
• Matching regular expressions on uncertain data

Describes a project that uses

Uses Software

• PERL
• AWK

This page was built for publication: Faster Regular Expression Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638033)