String-matching cannot be done by a two-head one-way deterministic finite automaton
type: Item
instance of: scholarly article
title: String-matching cannot be done by a two-head one-way deterministic finite automaton
zbMATH Open document ID: 0592.68070
DOI: 10.1016/0020-0190(86)90099-2
author: Ming Li
author: Yaacov Yesha
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
full work available at URL: https://hdl.handle.net/1813/6419
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 3952036
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: k-head finite automata, lower bounds
MaRDI profile type: Publication
OpenAlex ID: W1987107420
cites work: Fooling a two way automaton or one pushdown store is better than one counter for two way machines
cites work: Time-space-optimal string matching
cites work: Q3862379
cites work: Q3051378
cites work: k + 1 Heads Are Better than k
description: scientific article; zbMATH DE number 3952036