Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Multidimensional cel ...
Article

Multidimensional cellular automata and generalization of Fekete's lemma

Silvio Capobianco ORCID (1)
(1) School of Computer Science [Reykjavik]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2008
Last modified on
March 31, 2025
Volume 10
vol. 10:3
Automata, Logic and Semantics
DOI
10.46298/dmtcs.442
License
https://about.hal.science/hal-authorisation-v1
Indicators
1342
Views
734
Downloads

Multidimensional cellular automata and generalization of Fekete's lemma

Silvio Capobianco ORCID (1)
(1) School of Computer Science [Reykjavik]
Abstract
Fekete's lemma is a well-known combinatorial result on number sequences: we extend it to functions defined on d-tuples of integers. As an application of the new variant, we show that nonsurjective d-dimensional cellular automata are characterized by loss of arbitrarily much information on finite supports, at a growth rate greater than that of the support's boundary determined by the automaton's neighbourhood index.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • The Wasserstein Distance of Order 1 for Quantum Spin Systems on Infinite Lattices

    Archivio istituzionale della ricerca (Alma Mater Studiorum Università di Bologna)

    Authors : Giacomo De Palma ORCID, Dario Trevisan ORCID

    Journal reference : Volume 24, 2023, pp. 4237-4282

    DOI : 10.1007/s00023-023-01340-y

  • On Effective Convergence in Fekete’s Lemma and Related Combinatorial Problems in Information Theory

    Lecture notes in computer science

    Authors : Holger Boche ORCID, Yannik Böck ORCID, Christian Deppe ORCID

    Journal reference : Volume , 2025, pp. 286-313

    DOI : 10.1007/978-3-031-82014-4_12

  • Storage codes and recoverable systems on lines and grids

    Designs Codes and Cryptography

    Authors : Alexander Barg ORCID, Ohad Elishco ORCID, Ryan Gabrys ORCID, Geyang Wang ORCID, Eitan Yaakobi ORCID

    Journal reference : Volume 92, 2024, pp. 4145-4168

    DOI : 10.1007/s10623-024-01481-z

  • Approximating the hard square entropy constant with probabilistic methods

    The Annals of Probability

    Authors : Ronnie Pavlov ORCID

    Journal reference : Volume 40, 2012, pp.

    DOI : 10.1214/11-aop681

  • ON PANSIOT WORDS AVOIDING 3-REPETITIONS

    Electronic Archive of Ural Federal University (ELAR UrFU)

    Authors : IRINA A. GORBUNOVA, ARSENY M. SHUR ORCID

    Journal reference : Volume 23, 2012, pp. 1583-1594

    DOI : 10.1142/s0129054112400631
Preview
Loading PDF preview...