String matching with simple devices

With the help of a general simulation technique of deterministic finite two-way multi-head automata by automata with blind heads we show O ( n 2 / log n ) to be an upper time bound on string matching. This result is tight by a previously known lower bound.

Saved in:
Bibliographic Details
Published in:Information processing letters 2007-12, Vol.105 (1), p.32-34
Main Author: Petersen, Holger
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computational complexity
Computer science
control theory
systems
Exact sciences and technology
Miscellaneous
Simulation
String matching
Studies
Theoretical computing
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With the help of a general simulation technique of deterministic finite two-way multi-head automata by automata with blind heads we show O ( n 2 / log n ) to be an upper time bound on string matching. This result is tight by a previously known lower bound.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2007.07.011