String-matching cannot be done by a two-head one-way deterministic finite automaton
From MaRDI portal
Publication:1075776
DOI10.1016/0020-0190(86)90099-2zbMath0592.68070OpenAlexW1987107420MaRDI QIDQ1075776
Publication date: 1986
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6419
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