A Curtis-Hedlund-Lyndon theorem for Besicovitch and Weyl spaces

Johannes Müller, Christoph Spandl

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Global functions of cellular automata on state spaces equipped with the Cantor topology are well characterized by the Curtis-Hedlund-Lyndon theorem. In this paper, we develop a characterization of global functions of cellular automata on Z, if the state space is equipped by Weyl and Besicovitch topology. The necessary and sufficient condition for a function to be the global map of a cellular automaton is (1) a strong localization property, a condition that strengthen Lipschitz continuity, (2) the set of (Cantor) periodic states are positively invariant and (3) the function commutes (in the Weyl/Besicovitch sense) with the shift operator.

Original languageEnglish
Pages (from-to)3606-3615
Number of pages10
JournalTheoretical Computer Science
Volume410
Issue number38-40
DOIs
StatePublished - 6 Sep 2009

Keywords

  • Besicovitch topology
  • Cantor topology
  • Cellular automata
  • Curtis-Hedlund-Lyndon theorem
  • Weyl topology

Fingerprint

Dive into the research topics of 'A Curtis-Hedlund-Lyndon theorem for Besicovitch and Weyl spaces'. Together they form a unique fingerprint.

Cite this