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

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