RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive
Zap. Nauchn. Sem. LOMI, 1971 Volume 20, Pages 104–114 (Mi znsl2401)
This article is cited in 1 paper

On real-time recognition of the relation of occurrence

Yu. V. Matiyasevich


Abstract: It is shown that the relation "word $Q$ occurs in word $P$" is real-time recognizable by a Turing machine with two-dimensional tape.



Bibliographic databases:

© Steklov Math. Inst. of RAS, 2024