k one-way heads cannot do string-matching

DOI10.1145/167088.167111zbMath1310.68133OpenAlexW2064661842MaRDI QIDQ5248472

Tao Jiang, Ming Li

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167111

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithms on strings (68W32)

Related Items

Saving comparisons in the Crochemore-Perrin string-matching algorithm ⋮ Sensing versus nonsensing automata