Separating real-time and linear space recognition of languages on one-dimensional cellular automata

Abstract : In this article we will focus on a famous open question about algorithmiccomplexity classes on one dimensional cellular automata, and we willshow that if all problems recognizable in space n (where n is the length ofthe input) can be recognized in time n then for every space-constructiblefunction f all the problems that are recognizable in space f can berecognized in time f.
Document type :
Reports
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102258
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 10:51:26 AM
Last modification on : Sunday, April 28, 2019 - 1:23:07 AM

File

RR2006-10.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102258, version 1

Collections

Citation

Victor Poupet. Separating real-time and linear space recognition of languages on one-dimensional cellular automata. [Research Report] LIP RR-2006-10, Laboratoire de l'informatique du parallélisme. 2006, 2+14p. ⟨hal-02102258⟩

Share

Metrics

Record views

10

Files downloads

10