Space lower bounds for online pattern matching

DOI10.1016/j.tcs.2012.06.012zbMath1292.68180OpenAlexW2130314652MaRDI QIDQ390881

Markus Jalsenius, Raphaël Clifford, Benjamin Sach, Ely Porat

Publication date: 9 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.012

zbMATH Keywords

distance functionsonline pattern matchingspace lower boundswildcard-like properties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Pattern recognition, speech recognition (68T10) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Unnamed Item ⋮ Streaming pattern matching with \(d\) wildcards ⋮ Periodicity in data streams with wildcards ⋮ Streaming \(k\)-mismatch with error correcting and applications

Cites Work

• Unnamed Item
• The communication complexity of the Hamming distance problem
• Faster pattern matching with character classes using prime number encoding
• Private vs. common random bits in communication complexity
• String matching under a general matching relation
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Pattern Matching with Swaps
• Maintaining Stream Statistics over Sliding Windows
• Communication Complexity
• Exact and Approximate Pattern Matching in the Streaming Model