A Four Russians algorithm for regular expression pattern matching

DOI10.1145/128749.128755MaRDI QIDQ4302816zbMATH OpenOpenAlexFDO

Authors Gene Myers

Publication date 13 November 1994

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/128749.128755

zbMATH Keywords

finite automatonfour Russian paradigmnode listingpattern matchingregular expression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10) Parallel algorithms in computer science (68W10)

Recommendations

• New Algorithms for Regular Expression Matching
• A Subquadratic Algorithm for Approximate Regular Expression Matching
• A Boyer-Moore-style algorithm for regular expression pattern matching.
• A new regular grammar pattern matching algorithm
• scientific article; zbMATH DE number 1962812
• scientific article; zbMATH DE number 5717242
• A fast bit-parallel algorithm for matching extended regular expressions
• scientific article; zbMATH DE number 2080996
• Approximate matching of regular expressions
• Algorithms for pattern matching

Cited in

(38)

• Matching a set of strings with variable length don't cares
• An efficient null-free procedure for deciding regular language membership
• A faster algorithm for finding shortest substring matches of a regular expression
• Exact matching of RNA secondary structure patterns
• Regular expression searching on compressed text
• A subquadratic algorithm for approximate limited expression matching
• On the size of partial derivatives and the word membership problem
• From regular expression matching to parsing
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• Online recognition of dictionary with one gap
• Dictionary matching with a few gaps
• Fast and compact regular expression matching
• Mind the gap!
• Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA
• Faster algorithms for weighted recursive state machines
• Regular expression matching algorithm based on parameters setting
• Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism
• Compressing regular expressions' DFA table by matrix decomposition
• Dynamic set intersection
• Regular expression grouping optimization based on genetic algorithm
• New Algorithms for Regular Expression Matching
• Fast Searching in Packed Strings
• Faster Regular Expression Matching
• String matching with variable length gaps
• Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism
• Minimized Thompson NFA
• Tighter connections between Formula-SAT and shaving logs
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• From Regular Expression Matching to Parsing
• A succinct four Russians speedup for edit distance computation and one-against-many banded alignment
• Fast searching in packed strings
• Space-efficient representations for Glushkov automata
• scientific article; zbMATH DE number 7651219 (Why is no real title available?)
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• A unified view to string matching algorithms
• Text indexing for simple regular expressions
• Efficient matching of some fundamental regular expressions with backreferences
• Compact representations of automata for regular expression matching

This page was built for publication: A Four Russians algorithm for regular expression pattern matching

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