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

Victor Poupet (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Nous nous penchons, dans cet article, sur une question ouverte concernant les classes de complexité algorithmique sur automates cellulaires unidimensionels, et nous montrons que si tous les problèmes reconnaissables en espace linéaire sont reconnaissables en temps-réel alors pour toute fonction f constructible en espace, tout problème reconnaissable en espace f est reconnaissable en temps f.

Mots clés: Cellular automata; Language recognition; Linear space; Real-time

Mots clés: Automates cellulaires; Espace linéaire; Reconnaissance de langages; Temps réel

Domaines: Informatique [cs]

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⟩