String matching with simple devices

DOI10.1016/J.IPL.2007.07.011MaRDI QIDQ2380036zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• String Matching for the Novice
• scientific article; zbMATH DE number 1045407
• On string matching with mismatches
• Simple Optimal String Matching Algorithm
• Simple and efficient string matching with k mismatches
• String matching with involutions
• scientific article; zbMATH DE number 4078846
• String matching under a general matching relation
• Simple real-time constant-space string matching

Cites work

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

Cited in

(2)

• String-matching cannot be done by a two-head one-way deterministic finite automaton
• Refined simulation of multihead automata

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

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