Pattern matching with don't cares and few errors

DOI10.1016/J.JCSS.2009.06.002MaRDI QIDQ847263zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild

Publication date 12 February 2010

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2009/2244/

zbMATH Keywords

group testingpattern matchingstring algorithmsrandomised algorithms

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Randomized algorithms (68W20)

Recommendations

• k-Mismatch with Don’t Cares
• Matching with don't-cares and a small number of mismatches
• A filtering algorithm for k-mismatch with don't cares
• On pattern matching with \(k\) mismatches and few don't cares
• Approximate subset matching with don't cares

Cites work

• scientific article; zbMATH DE number 5604063 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 65702 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 2119723 (Why is no real title available?)
• scientific article; zbMATH DE number 5262869 (Why is no real title available?)
• scientific article; zbMATH DE number 956611 (Why is no real title available?)
• A Linear Size Index for Approximate Pattern Matching
• A fast string searching algorithm
• A filtering algorithm for \(k\)-mismatch with don't cares
• Born again group testing: Multiaccess communications
• Dictionary matching and indexing with errors and don't cares
• Distributed broadcast in radio networks of unknown topology.
• Efficient string matching with k mismatches
• Explicit Non-adaptive Combinatorial Group Testing Schemes
• Fast Pattern Matching in Strings
• Fast algorithms for approximately counting mismatches
• Faster algorithms for string matching with k mismatches
• Fundamentals of Computation Theory
• Generalized String Matching
• Maximally Efficient Two‐Stage Screening
• Nonrandom binary superimposed codes
• Selective families, superimposed codes, and broadcasting on unknown radio networks. (Extended abstract)
• Simple deterministic wildcard matching
• Verifying candidate matches in sparse and wildcard matching

Cited in

(19)

• Low-weight superimposed codes and related combinatorial structures: bounds and applications
• On pattern matching with \(k\) mismatches and few don't cares
• Functional and Logic Programming
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Approximate subset matching with don't cares
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• k-Mismatch with Don’t Cares
• Generalized framework for group testing: queries, feedbacks and adversaries
• scientific article; zbMATH DE number 7758315 (Why is no real title available?)
• Bounds and algorithms for generalized superimposed codes
• Streaming pattern matching with \(d\) wildcards
• Subquadratic non-adaptive threshold group testing
• On the average-case complexity of pattern matching with wildcards
• From coding theory to efficient pattern matching
• The Negligible and Yet Subtle Cost of Pattern Matching
• Matching with don't-cares and a small number of mismatches
• A filtering algorithm for \(k\)-mismatch with don't cares
• scientific article; zbMATH DE number 5717259 (Why is no real title available?)
• A simple algorithm for approximating the text-to-pattern Hamming distance

Describes a project that uses

Uses Software

• AETG

This page was built for publication: Pattern matching with don't cares and few errors

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