String matching with simple devices

DOI10.1016/j.ipl.2007.07.011zbMath1184.68327OpenAlexW2006669295MaRDI QIDQ2380036

Holger Petersen

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.07.011

zbMATH Keywords

computational complexitystring matchingtheory of computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• \(k\) one-way heads cannot do string-matching
• String-matching cannot be done by a two-head one-way deterministic finite automaton
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines
• String-matching on ordered alphabets
• Three one-way heads cannot do string matching
• The zooming method: A recursive approach to time-space efficient string-matching
• Time-space-optimal string matching
• On maximal suffixes and constant-space linear-time versions of KMP algorithm.
• Fast Pattern Matching in Strings
• Two-way string-matching

This page was built for publication: String matching with simple devices