nach oben

Natural Computing

Erschienen in:

01.12.2013

Towards intrinsically universal asynchronous CA

verfasst von: Thomas Worsch

Erschienen in: Natural Computing | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider asynchronous one-dimensional cellular automata (CA). It is shown that there is one with von Neumann neighborhood of radius 1 which can simulate each asynchronous one-dimensional cellular automaton. Analogous constructions are described for α-asynchronous CA (where each cell independently enters a new state with probability α, and for “neighborhood independent” asynchronous CA (where never two cells are updated simultaneously if one is in the neighborhood of the other). This also gives rise to a construction for so-called fully asynchronous CA (where in each step exactly one cell is updated).

Vorheriger Artikel Foreword: asynchronous cellular automata and applications

Nächster Artikel First steps on asynchronous lattice-gas models with an application to a swarming rule

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Arrighi P, Schabanel N, Theyssier G (2012) Intrinsic simulations between stochastic cellular automata. In: Proceedings automata/JAC 2012, pp 208–224

Bandini S, Bonomi A, Vizzari G (2010) What do we mean by asynchronous CA? A reflection on types and effects of asynchronicity. In: Bandini S, Manzoni S, Umeo H, Vizzari G (eds) Proceedings ACRI 2010. LNCS, vol 6350. Springer, Heidelberg, pp 385–394

Bouré O, Fatès N, Chevrier V (2012) Probing robustness of cellular automata through variations of asynchronous updating. Nat Comput 11(4):553–564MathSciNetCrossRef

Delorme M, Mazoyer J, Ollinger N, Theyssier G (2011) Bulking II: classifications of cellular automata. Theor Comput Sci 412(30):3881–3905MathSciNetCrossRefMATH

Dennunzio A, Formenti E, Manzoni L, Mauri G (2012) m-asynchronous cellular automata. In: Proceedings ACRI 2012. LNCS, vol 7495. Springer, Heidelberg, pp 653–662

Durand-Lose JO (2000) Reversible space–time simulation of cellular automata. Theor Comput Sci 246(1–2):117–129MathSciNetCrossRefMATH

Fatès N, Gerin L (2008) Examples of fast and slow convergence of 2D asynchronous cellular systems. In: Umeo H et al (eds) Proceedings ACRI 2008. Springer, Heidelberg, pp 184–191

Golze U (1978) (A-)synchronous (non-)deterministic cell spaces simulating each other. J Comput Syst Sci 17(2):176–193MathSciNetCrossRefMATH

Lee J, Adachi S, Peper F, Morita K (2004) Asynchronous game of life. Physica D 194(3–4):369–384MathSciNetCrossRefMATH

Nakamura K (1974) Asynchronous cellular automata and their computational ability. Syst Comput Control 5(5):58–66

Ollinger N (2008) Universalities in cellular automata: a (short) survey. In: Durand B (ed) Proceedings JAC 2008, Uze, France, pp 102–118

Regnault D, Schabanel N, Thierry E (2009) Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority. Theor Comput Sci 410(47–49):4844–4855MathSciNetCrossRefMATH

Schuhmacher A (2012) Simulationsbegriffe bei asynchronen Zellularautomaten. Report for a student seminar

Worsch T (2010) A note on (intrinsically?) universal asynchronous cellular automata. In: Fatès N, Kari J, Worsch T (eds) Proceedings Automata 2010, Nancy, France, pp 339–350

Worsch T (2012a) (Intrinsically?) universal asynchronous cellular automata. In: Sirakoulis G, Bandini S (eds) Proceedings ACRI 2012. LNCS, vol 7495. Springer, Heidelberg, pp 689–698

Worsch T (2012b) (Intrinsically?) universal asynchronous cellular automata II. In: Formenti E (ed) exploratory papers proceedings ACRI 2012. LNCS. Springer, Heidelberg, pp 38–51

Worsch T, Nishio H (2009) Achieving universality of CA by changing the neighborhood. J Cell Autom 4(3):237–246MathSciNetMATH

Titel: Towards intrinsically universal asynchronous CA
verfasst von: Thomas Worsch
Publikationsdatum: 01.12.2013
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 4/2013
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-013-9388-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2013

Kernel clustering using a hybrid memetic algorithm

Foreword: asynchronous cellular automata and applications

On computational complexity of graph inference from counting

A review of morphogenetic engineering

Expanding the landscape of biological computation with synthetic multicellular consortia

Special issue on the frontiers of natural computing