String-matching cannot be done by a two-head one-way deterministic finite automaton

DOI10.1016/0020-0190(86)90099-2zbMath0592.68070OpenAlexW1987107420MaRDI QIDQ1075776

Yaacov Yesha, Ming Li

Publication date: 1986

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

Full work available at URL: https://hdl.handle.net/1813/6419

zbMATH Keywords

Kolmogorov complexityk-head finite automata, lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Formal languages and automata (68Q45)

Related Items

String-matching cannot be done by a two-head one-way deterministic finite automaton, String matching with simple devices, Remarks on string-matching and one-way multihead automata, Saving comparisons in the Crochemore-Perrin string-matching algorithm, One-reversal counter machines and multihead automata: revisited, One-Reversal Counter Machines and Multihead Automata: Revisited, Three one-way heads cannot do string matching

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Time-space-optimal string matching
• k + 1 Heads Are Better than k