Bruno Durand ; Enrico Formenti ; Georges Varouchas - On undecidability of equicontinuity classification for cellular automata

dmtcs:2302 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03) - https://doi.org/10.46298/dmtcs.2302
On undecidability of equicontinuity classification for cellular automata

Authors: Bruno Durand 1; Enrico Formenti ORCID-iD1; Georges Varouchas 1

  • 1 Laboratoire d'informatique Fondamentale de Marseille - UMR 6166

Equicontinuity classification is a popular classification of cellular automata based on their dynamical behavior. In this paper we prove that most of its classes are undecidable.

https://doi.org/10.46298/dmtcs.2302
Source: HAL:hal-01183309v1
Volume: DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03)
Section: Proceedings
Published on: January 1, 2003
Imported on: November 21, 2016
Keywords: classification,cellular automata,undecidability,discrete dynamical systems,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

12 Documents citing this article

Share and export

Consultation statistics

This page has been seen 230 times.
This article's PDF has been downloaded 174 times.