𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Subquadratic Algorithm for Approximate Regular Expression Matching

✍ Scribed by S. Wu; U. Manber; E. Myers

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
673 KB
Volume
19
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

The main result of this paper is an algorithm for approximate matching of a regular expression of size (m) in a text of size (n) in time (O\left(n m / \log _{d+2} n\right)), where (d) is the number of allowed errors. This algorithm is the first (o(m n)) algorithm for approximate matching to regular expressions. 1995 Academic Press. Inc.

πŸ“œ SIMILAR VOLUMES

A simple matching algorithm for regular
A simple matching algorithm for regular bipartite graphs
✍ Kazuhisa Makino; Takashi Takabatake; Satoru Fujishige πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 62 KB

We consider the perfect matching problem for a βˆ†-regular bipartite graph with n vertices and m edges, i.e., 1 2 nβˆ† = m, and present a new O(m + n log n log βˆ†) algorithm. Cole and Rizzi, respectively, gave algorithms of the same complexity as ours, Schrijver also devised an O(mβˆ†) algorithm, and the b

A parallel algorithm for approximate reg
A parallel algorithm for approximate regularity
✍ Laurence Boxer; Russ Miller πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 77 KB

Spatial regularity amidst a seemingly chaotic image is often meaningful. Many papers in computational geometry are concerned with detecting some type of regularity via exact solutions to problems in geometric pattern recognition. However, real-world applications often have data that is approximate,

A new algorithm for linear regular tree
A new algorithm for linear regular tree pattern matching
✍ Priti Shankar; Amitranjan Gantait; A.R. Yuvaraj; Maya Madhavan πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 129 KB

We consider the problem of linear regular tree pattern matching and describe a new solution based on a bottom up technique. Current bottom up techniques preprocess the patterns and construct a ΓΏnite state tree pattern matching automaton for the purpose. Though matching time is linear in the size of

A new regular grammar pattern matching a
A new regular grammar pattern matching algorithm
✍ Bruce W. Watson πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 155 KB

This paper presents a Boyer-Moore type algorithm for regular grammar pattern matching, answering a variant of an open problem posed by Aho (Pattern Matching in Strings, Academic Press, New York, 1980, p. 342). The new algorithm handles patterns speciΓΏed by regular (left linear) grammars-a generaliza