Three one-way heads cannot do string matching

DOI10.1016/S0022-0000(05)80020-0zbMath0802.68056MaRDI QIDQ1318467

Mihály Geréb-Graus, Ming Li

Publication date: 11 December 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

string matchingdeterministic finite automaton

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Related Items

String matching with simple devices ⋮ Saving comparisons in the Crochemore-Perrin string-matching algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• String-matching cannot be done by a two-head one-way deterministic finite automaton
• Tape versus queue and stacks: The lower bounds
• An information-theoretic approach to time bounds for on-line computation
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines
• A fast string searching algorithm
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• Fast Pattern Matching in Strings