Separating real-time and linear space recognition of languages on one-dimensional cellular automata - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

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

(1)
1

Résumé

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.
Fichier principal
Vignette du fichier
RR2006-10.pdf (259.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102258 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102258 , version 1

Citer

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⟩
7 Consultations
11 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More