About
Contact
Help
Sending publications
How to publish
Advanced Search
View Item 
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse byCommunities and CollectionsDateAuthorsTitlesSubjectsThis CollectionDateAuthorsTitlesSubjects

My Account

Login to my accountRegister
Biblioteca Digital - Universidad de Chile
Revistas Chilenas
Repositorios Latinoamericanos
Tesis LatinoAmericanas
Tesis chilenas
Related linksRegistry of Open Access RepositoriesOpenDOARGoogle scholarCOREBASE
My Account
Login to my accountRegister

Communication complexity and intrinsic universality in cellular automata

Artículo
Thumbnail
Open/Download
IconGoles_E.pdf (509.1Kb)
Publication date
2011
Metadata
Show full item record
Cómo citar
Goles Chacc, Eric,
Cómo citar
Communication complexity and intrinsic universality in cellular automata
.
Copiar
Cerrar

Author
  • Goles Chacc, Eric,;
  • Meunier, P.-E.;
  • Rapaport Zimermann, Iván;
  • Theyssier, G.;
Abstract
The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be ‘‘universal’’, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space–time rescaling and it is intrinsic to the model of cellular automata. Intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal.
General note
Artículo de publicación ISI
Patrocinador
Partially supported by programs Fondap and Basal-CMM, Fondecyt 1070022 (E.G) and Fondecyt 1090156 (I.R.).
Identifier
URI: https://repositorio.uchile.cl/handle/2250/125510
DOI: doi:10.1016/j.tcs.2010.10.005
Quote Item
Theoretical Computer Science 412 (2011) 2–21
Collections
  • Artículos de revistas
xmlui.footer.title
31 participating institutions
More than 73,000 publications
More than 110,000 topics
More than 75,000 authors
Published in the repository
  • How to publish
  • Definitions
  • Copyright
  • Frequent questions
Documents
  • Dating Guide
  • Thesis authorization
  • Document authorization
  • How to prepare a thesis (PDF)
Services
  • Digital library
  • Chilean academic journals portal
  • Latin American Repository Network
  • Latin American theses
  • Chilean theses
Dirección de Servicios de Información y Bibliotecas (SISIB)
Universidad de Chile

© 2020 DSpace
  • Access my account