Lecture Notes in Computer Science 6350 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Stefania Bandini Sara Manzoni Hiroshi Umeo Giuseppe Vizzari (Eds.) Cellular Automata 9th International Conference on CellularAutomata for Research and Industry,ACRI 2010 Ascoli Piceno, Italy, September 21-24, 2010 Proceedings 1 3 VolumeEditors StefaniaBandini ComplexSystemsandArtificialIntelligenceResearchCenter UniversityofMilano-Bicocca VialeSarca336/14,Milano,Italy E-mail:[email protected] SaraManzoni ComplexSystemsandArtificialIntelligenceResearchCenter UniversityofMilano-Bicocca VialeSarca336/14,Milano,Italy E-mail:[email protected] HiroshiUmeo FacultyofInformationScienceandTechnology UniversityofOsakaElectro-Communication 572-8530Neyagawa,Osaka,Japan E-mail:[email protected] GiuseppeVizzari ComplexSystemsandArtificialIntelligenceResearchCenter UniversityofMilano-Bicocca VialeSarca336/14,Milano,Italy E-mail:[email protected] LibraryofCongressControlNumber:2010934512 CRSubjectClassification(1998):F.1.1,F.1,F.2.2,I.6,C.2 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-642-15978-8SpringerBerlinHeidelbergNewYork ISBN-13 978-3-642-15978-7SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. springer.com ©Springer-VerlagBerlinHeidelberg2010 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper 06/3180 Foreword Thisvolumecollectsthepapersselectedforpresentationatthe9thInternational Conference on Cellular Automata for Researchand Industry (ACRI 2010),held in Ascoli Piceno (Italy), September 21-24, 2010. ACRI conferences have been offering since 1994 a biennial scientific meeting tobothscientistsandinnovationmanagersinacademiaandindustriytoexpress anddiscusstheirviewpointsoncurrentandfuturetrends,challenges,andstate- of-the-art solutions to various problems in the fields of arts, biology, chemistry, communication,ecology,economy,engineering,networks,physics,socialscience, and traffic control. ACRI 2010 was organized by the Complex Systems and Ar- tificial Intelligence (CSAI) research center of the University of Milano-Bicocca as a forum for the presentation and discussion of specialized results as well as general contributions to the growth of the cellular automata approach and its application. Cellular automata represent a very powerful approachto the study of spatio-temporalsystems where complex phenomena are built up out ofmany simplelocalinteractions.TheACRIconferenceserieswasfirstorganizedinItaly (ACRI1994inRende,ACRI1996inMilan,andACRI1998inTrieste),andafter havingmovedtootherEuropeanandinternationalsettings,thisyearcameback to Italy: ACRI 2000 in Karlsruhe (Germany), ACRI 2002 in Geneva (Switzer- land), ACRI 2004 in Amsterdam (The Netherlands), ACRI 2006 in Perpignan (France), and ACRI 2008 in Yokohama (Japan). Inorderto giveaperspective inwhichboth theoreticalandapplicationalas- pectsofcellularautomatacontributetothegrowthofthearea,thisbookmirrors thestructureoftheconference,groupingthe74papersintotwomainparts.The firstpartcollectspaperspresentedaspartofthe mainconferenceandorganized according to six main topics: (1) theoretical results on cellular automata, (2) modeling and simulation with cellular automata, (3) CA dynamics, control and synchronization,(4)codesandcryptographywithcellularautomata,(5)cellular automataandnetworks,and(6)CA-basedhardware.Thesecondpartofthevol- ume is dedicated to contributions presented during the ACRI 2010 workshops on theoretical advances, specifically Asynchronous Cellular Automata (chairs: Alberto Dennunzio, Enrico Formenti, and Marco Tomassini), and challenging application contexts for cellular automata:Crowds and CA (3rd edition, chairs: Sara Manzoni and Shin Morishita), Traffic and CA (chairs: Katsuhiro Nishi- nari and Andreas Schadschneider), and the International Workshop of Natural Computing (chairs: Ferdinand Peper and Hiroshi Umeo). Many people contributed to the success of ACRI 2010 and to the creation of this volume, from the initial idea to its implementation. Our first acknowl- edgement is to all the scientists that submitted their works, and to all Program VI Foreword Committee members and reviewers for their precious collaboration. A special thanks for their hospitality to the University of Camerino (in particular to Emanuela Merelli and Flavio Corradini), Centro Studi Piceno, the municipality of Ascoli Piceno, and Fondazione Casse di Risparmio della Provincia di Ascoli Piceno,andforits generouscontributiontothe realizationofthis volumetothe University of Milano-Bicocca. Aspecialacknowledgementalsotoallthepeopleinvolvedintheorganization ofACRI2010(inparticulartoPaolaLembo,GiorgiaMalvolta,LorenzaManenti, and Luca Manzoni) whose work was fundamental for the actual success of the event. Finally, we would like to thank the Department of Computer Science, Sys- tems and Communication of the University of Milano–Bicocca, and those that financially supported the congress:illycaff`e and Fondazione Casse di Risparmio della Provincia di Ascoli Piceno. July 2010 Stefania Bandini Sara Manzoni Hiroshi Umeo Giuseppe Vizzari Organization ACRI 2010 was organized by the Complex Systems and Artificial Intelligence research center (CSAI) and Artificial Intelligence Lab (L.INT.AR.) of the De- partment of Computer Science, Systems and Communication (DISCo) of the University of Milano–Bicocca, and hosted by the University of Camerino. Organizing Committee Sara Manzoni (Chair), Paola Lembo, Giorgia Malvolta, Lorenza Manenti, Luca Manzoni, Emanuela Merelli, Giuseppe Vizzari. Congress Chairs Stefania Bandini University of Milano-Bicocca Hiroshi Umeo University of Osaka Steering Committee Stefania Bandini University of Milano-Bicocca, Italy Bastien Chopard University of Geneva, Switzerland Giancarlo Mauri University of Milano-Bicocca, Italy Hiroshi Umeo University of Osaka, Japan Thomas Worsch University of Karlsruhe, Germany Program Committee Susumu Adachi (Japan) Nazim Fats (France) Andrew Adamatzky (UK) Alfons Hoekstra (The Netherlands) Franco Bagnoli (Italy) Teijiro Isokawa (Japan) Stefania Bandini (Italy) Francisco Jimnez (Spain) Olga Bandman (Russia) Toshihiko Komatsuzaki (Japan) Belgacem Ben Youssef (Canada) Anna T. Lawniczak (Canada) Debashish Chowdhury (India) Jia Lee (Japan) Bastien Chopard (Switzerland) Pradipta Maji (India) Alberto Dennunzio (Italy) Danuta Makowiec (Poland) Andreas Deutsch (Germany) Sara Manzoni (Italy) Salvatore Di Gregorio (Italy) Nobuyuki Matsui (Japan) Michel Droz (Switzerland) Giancarlo Mauri (Italy) Samira El Yacoubi (France) Michael Meyer-Hermann (Germany) VIII Organization Angelo Mingarelli (Canada) Domenico Talia (Italy) Shin Morishita (Japan) Gianluca Tempesti (Switzerland) Katsuhiro Nishinari (Japan) Marco Tomassini (Switzerland) Hidenosuke Nishio (Japan) Leen Torenvliet (The Netherlands) Ferdinand Peper (Japan) Hiroshi Umeo (Japan) Roberto Serra (Italy) Giuseppe Vizzari (Italy) Georgios Sirakoulis (Greece) Burton Voorhees (Canada) Furio Suggi Liverani (Italy) Thomas Worsch (Germany) Peter Sloot (The Netherlands) G. Keith Still (UK) Workshop Chairs Asynchronous CA Alberto Dennunzio (Universita` di Milano-Bicocca, Italy) Enrico Formenti (Universit´e de Nice - Sophia Antipolis, France) Marco Tomassini (Universit´e de Lausanne, Switzerland) Crowds and CA Sara Manzoni (Universita` di Milano-Bicocca, Italy) Shin Morishita (Yokohama National University, Japan) Traffic and CA Katsuhiro Nishinari (University of Tokyo, Japan) Andreas Schadschneider (Universita¨t zu Ko¨ln, Germany) Natural Computing Ferdinand Peper (National Institute of Information and Communications Technology, Japan) Hiroshi Umeo (University of Osaka Electro-Communication,Japan) Yasuhiro Suzuki (Nagoya University, Japan) Table of Contents Theoretical Results on Cellular Automata Information Transfer among Coupled Random Boolean Networks ...... 1 Chiara Damiani, Stuart A. Kauffman, Roberto Serra, Marco Villani, and Annamaria Colacci Open Environment for 2d Lattice-Grain CA ......................... 12 Guillaume Cottenceau and Dominique D´es´erable All-to-All Communication with CA Agents by Active Coloring and Acknowledging .................................................. 24 Patrick Ediger and Rolf Hoffmann The Sandpile Model: ParallelizationofEfficient Algorithms for Systems with Shared Memory ............................................. 35 Sebastian Frehmel Theory and Application of Equal Length Cycle Cellular Automata (ELCCA) for Enzyme Classification ................................ 46 Soumyabrata Ghosh, Tirthankar Bachhar, Nirmalya S. Maiti, Indrajit Mitra, and P. Pal Chaudhuri Cellular Automata Model for Size Segregation of Particles............. 58 Toshihiko Komatsuzaki and Yoshio Iwata Convex Hulls on Cellular Automata ................................ 69 Luidnel Maignan and Fr´ed´eric Gruau Square Kufic Pattern Formation by Asynchronous Cellular Automata... 79 Seyyed Amir Hadi Minoofam and Azam Bastanfard Modeling and Simulation with Cellular Automata Development and Calibration of a Preliminary Cellular Automata Model for Snow Avalanches ....................................... 83 Maria Vittoria Avolio, Alessia Errera, Valeria Lupiano, Paolo Mazzanti, and Salvatore Di Gregorio Tracking Uncertainty in a Spatially Explicit Susceptible-Infected Epidemic Model ................................................. 95 Jan M. Baetens and Bernard De Baets A ProximalSpace Approach for Embedding Urban Geography into CA Models ......................................................... 106 Ivan Blecic, Arnaldo Cecchini, and Giuseppe A. Trunfio X Table of Contents Bone Remodelling: A Complex Automata-Based Model Running in BioShape ...................................................... 116 Diletta Cacciagrano, Flavio Corradini, and Emanuela Merelli CANv2: A Hybrid CA Model by Micro and Macro–dynamics Examples ....................................................... 128 Claudia R. Calidonna, Adele Naddeo, Giuseppe A. Trunfio, and Salvatore Di Gregorio Simulation of Traffic Flow at a Signalised Intersection ................ 138 Somayyeh Belbasi and M. Ebrahim Foulaadvand A Novel Method for Simulating Cancer Growth...................... 142 Mehrdad Ghaemi, Omid Naderi, and Zahra Zabihinpour Towards Cellular Automata Football Models with Mentality Accounting...................................................... 149 Alexander Makarenko, Dmitry Krushinski, Anton Musienko, and Boris Goldengorin The Complexity of Three-Dimensional Critical Avalanches ............ 153 Carolina Mej´ıa and J. Andr´es Montoya Using Cellular Automata on a Graph to Model the Exchanges of Cash and Goods ...................................................... 163 Ranaivo Mahaleo Razakanirina and Bastien Chopard Montebello: A Metapopulation Based Model of Carcinogenesis......... 173 David Tuck, Willard Miranker, and Jose Costa CA Dynamics, Control and Synchronization Towards Generalized Measures Grasping CA Dynamics ............... 177 Jan M. Baetens and Bernard De Baets Synchronization and Control of Cellular Automata ................... 188 Franco Bagnoli, Samira El Yacoubi, and Rau´l Rechtman Discovery by Genetic Algorithm of Cellular Automata Rules for Pattern Reconstruction Task ...................................... 198 Anna Piwonska and Franciszek Seredynski Addition of Recurrent Configurations in Chip Firing Games: Finding Minimal Recurrent Configurations with Markov Chains ............... 209 Matthias Schulz A Seven-State Time-Optimum Square Synchronizer .................. 219 Hiroshi Umeo and Keisuke Kubo