Realtime subshifts

Kurka, P; Maass A.

Abstract

We generalize the class of sofic subshifts, which correspond to regular languages, to subshifts accepted by either nondeterministic or deterministic Turing 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.

Más información

Título según WOS: Realtime subshifts
Título según SCOPUS: Realtime subshifts
Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 237
Número: 1-2
Editorial: Elsevier
Fecha de publicación: 2000
Página de inicio: 307
Página final: 325
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0304397598001923
DOI:

10.1016/S0304-3975(98)00192-3

Notas: ISI, SCOPUS