Remarks on string-matching and one-way multihead automata

DOI10.1016/0020-0190(87)90157-8zbMath0653.68080OpenAlexW2062687935MaRDI QIDQ1108049

Marek Chrobak, Wojciech Rytter

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90157-8

zbMATH Keywords

complexitystring matchingon-line computationmultihead automata

Mathematics Subject Classification ID

Related Items (2)

Multihead one-way finite automata ⋮ One-way multihead finite automata and 2-bounded languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• String-matching cannot be done by a two-head one-way deterministic finite automaton
• A fast string searching algorithm
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Algorithmic Information Theory
• Fast Pattern Matching in Strings

This page was built for publication: Remarks on string-matching and one-way multihead automata