Citation
P. Kurka et A. Maass, Realtime subshifts, THEOR COMP, 237(1-2), 2000, pp. 307-325
Citations number
14
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975
→ ACNP
Volume
237
Issue
1-2
Year of publication
2000
Pages
307 - 325
Database
ISI
SICI code
0304-3975(20000428)237:1-2<307:RS>2.0.ZU;2-U
Abstract
We generalize the class of sofic subshifts, which correspond to regular lan
guages, to subshifts accepted by either nondeterministic or deterministic T
uring machines in real time. We show that every substitutive system can be
accepted by a deterministic Turing machine in real time. (C) 2000 Elsevier
Science B.V. All rights reserved.