Pattern matching with don't cares and few errors

DOI10.1016/J.JCSS.2009.06.002zbMATH Open1186.68407OpenAlexW2049842402MaRDI QIDQ847263FDOQ847263

Klim Efremenko, Raphaël Clifford, 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/

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

zbMATH Keywords

group testingpattern matchingstring algorithmsrandomised algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• Title not available (Why is that?)
• On the average-case complexity of pattern matching with wildcards
• The Negligible and Yet Subtle Cost of Pattern Matching
• Functional and Logic Programming
• k-Mismatch with Don’t Cares
• Generalized framework for group testing: queries, feedbacks and adversaries
• Streaming pattern matching with \(d\) wildcards
• Title not available (Why is that?)
• Subquadratic non-adaptive threshold group testing
• A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance
• Low-weight superimposed codes and related combinatorial structures: bounds and applications
• On pattern matching with \(k\) mismatches and few don't cares
• Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams
• Bounds and algorithms for generalized superimposed codes
• Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
• Approximate subset matching with don't cares

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)