Alonso Castillo-Ramirez Pedro P. B. de Oliveira (Eds.) Cellular Automata 5 2 and Discrete 5 1 1 S Complex Systems C N L 25th IFIP WG 1.5 International Workshop, AUTOMATA 2019 Guadalajara, Mexico, June 26–28, 2019 Proceedings 123 Lecture Notes in Computer Science 11525 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board Members David Hutchison Lancaster University, Lancaster, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Zurich, Switzerland John C. Mitchell Stanford University, Stanford, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel C. Pandu Rangan Indian Institute of Technology Madras, Chennai, India Bernhard Steffen TU Dortmund University, Dortmund, Germany Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA More information about this series at http://www.springer.com/series/7407 Alonso Castillo-Ramirez (cid:129) Pedro P. B. de Oliveira (Eds.) Cellular Automata and Discrete Complex Systems 25th IFIP WG 1.5 International Workshop, AUTOMATA 2019 Guadalajara, Mexico, June 26–28, 2019 Proceedings 123 Editors AlonsoCastillo-Ramirez PedroP. B. deOliveira University of Guadalajara Mackenzie Presbyterian University Guadalajara, Mexico SaoPaulo, Brazil ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-030-20980-3 ISBN978-3-030-20981-0 (eBook) https://doi.org/10.1007/978-3-030-20981-0 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©IFIPInternationalFederationforInformationProcessing2019 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictionalclaimsin publishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface This volume contains the full papers presented at the 25th International Workshop on CellularAutomata(CA)andDiscreteComplexSystems(DCS),AUTOMATA2019,held during June 26–28, 2019, at the University Center of Exact Sciences and Engineering, CUCEI,UniversityofGuadalajara,México.Theconferencewastheofficialannualevent ofthe International Federation for Information Processing (IFIP),Working Group 5,on CAandDCS,oftheTechnicalCommittee1,onFoundationsofComputerScience. AUTOMATA2019ispartofanannualseriesofconferencesestablishedin1995as a collaboration forum between researchers in CA and DCS. Current topics of the conference include, but are not limited to, dynamical, topological, ergodic, and alge- braicaspectsofCAandDCS,algorithmicandcomplexityissues,emergentproperties, formal languages, symbolic dynamics, tilings, models of parallelism and distributed systems, timing schemes, synchronous versus asynchronous models, phenomenologi- cal descriptions, scientific modeling, and practical applications. AUTOMATA 2019 was the fourth time that the conference took place in a Latin American country, the last time having been in Santiago, Chile, in 2011. As a cele- bration of its Silver Jubilee, the event had a special session commemorating the date. We had three invited talks given by Pablo Arrighi, Hector Zenil, and Tullio Ceccherini-Silberstein; we sincerely thank them for accepting the invitation and their very interesting presentations. The abstracts of the invited talks are included here. Wereceivedtensubmissionsasfullpapersfortheconference.Eachsubmissionwas reviewedbythreemembersoftheProgramCommittee.Basedonthesereviewsandan open discussion, seven papers were accepted to be presented at the conference and to be included in the proceedings. We thank all authors for their contributions and hard work that made this event possible. Theconferenceprogramalsoinvolvedshortpresentationsofexploratorypapersthat arenotincludedintheseproceedings,andwewishtoextendourthankstotheauthors of the exploratory submissions. We are indebted to the Steering Committee, Program Committee, and additional reviewersfortheirvaluablehelpduringthelastmonths.Weacknowledgethegenerous funding provided by the IFIP and the University of Guadalajara toward the organi- zation of this event. We are very grateful for the support of the local Organizing Committee and the authorities of CUCEI; in particular, our sincere thanks to Dr. Humberto Gutiérrez Pulido, Head of the Department of Mathematics, and to Dr. Ruth Padilla Muñoz, RectorofCUCEI.Finally,weacknowledgetheexcellentcooperationfromtheLecture NotesinComputerScienceteamofSpringerfortheirhelpinproducingthisvolumein time for the conference. April 2019 Alonso Castillo-Ramirez Pedro P. B. de Oliveira Organization Steering Committee Enrico Formenti Université Côte d’Azur, France Jan Baetens Ghent University, Belgium Jarkko Kari University of Turku, Finland Pedro de Oliveira Universidade Presbiteriana Mackenzie, Brazil Turlough Neary University of Zurich and ETH Zurich, Switzerland Program Committee Alberto Dennunzio Università degli Studi di Milano-Bicocca, Italy Alonso Castillo-Ramirez Universidad de Guadalajara, México (Co-chair) Andrew Adamatzky University of the West of England, UK Edgardo Ugalde Universidad Autónoma de San Luis Potosí, México Enrico Formenti Université Côte d’Azur, France Guillaume Theyssier CNRS and Aix Marseille Université, France Hector Zenil SciLifeLab and Karolinska Institute, Sweden Henryk Fukś Brock University, Canada Ilkka Törmä University of Turku, Finland Jan Baetens Ghent University, Belgium Janko Gravner University of California Davis, USA Jarkko Kari University of Turku, Finland Katsunobu Imai Hiroshima University, Japan Luciano Margara University of Bologna, Italy Martin Kutrib Justus-Liebig-Universität Gießen, Germany Maximilien Gadouleau Durham University, UK Nazim Fatès Inria Nancy, France Paola Flocchini University of Ottawa, Canada PedrodeOliveira(Co-chair) Universidade Presbiteriana Mackenzie, Brazil Pietro Di Lena University of Bologna, Italy Reem Yassawi Université Claude Bernard Lyon 1, France Siamak Taati University of Groningen, The Netherlands Thomas Worsch Karlsruhe Institute of Technology, Germany Turlough Neary University of Zurich and ETH Zurich, Switzerland viii Organization Additional Reviewers Kévin Perrot Luca Manzoni Antonio E. Porreca Ville Salo Simon Beier Local Organizing Committee Alonso Castillo-Ramirez Humberto Gutiérrez Pulido Osbaldo Mata Gutiérrez María de la Paz Suárez Fernández Juan Manuel Márquez Bobadilla Abstracts of Invited Talks Quantum Cellular Automata: Computability and Universality P. Arrighi Aix-Marseille University, UniversitédeToulon, CNRS, LIS,Marseille, andIXXI, Lyon,France [email protected] Thistalkwillprovideanoverview ofthe fieldofQuantumCellularAutomata(QCA). QCA consist in an array of identical finite-dimensional quantum systems. The whole array evolves in discrete time steps by iterating a linear operator G. Moreover this global evolution G is shift-invariant (it acts everywhere in the same way), causal (information cannot be transmitted faster than some fixed number of cells per time step), and unitary (the condition required by the postulate of evolutions in quantum theory, akin to reversibility). I will motivate their studies through the distinction between finite-dimensional quantum evolutions (unitary matrices, a.k.a quantum automata) and infinite-dimensional quantum evolutions (unitary operators, a.k.a operators).Itturnsoutthatbasicquestionssurroundingcomputabilityanduniversality had only been solved for quantum automata, and not for quantum operators. We addressedthequestionoftheircomputabilityin[1],buildinguponastructuraltheorem that actually decomposes the axiomatic version of QCA [9, 17] into an infinitely repeatingquantumcircuitoflocalgates[7,8],whichwewillrecall.Wealsoaddressed thequestion oftheuniversality ofquantum operatorsinaseries ofworks[2–4]which wewillsummarize,andrelatetothefascinatingquestionofhowmuchparticlephysics can be recast in terms of QCA [6, 10, 13, 18]. In all of these results, quantum infor- mationflowsonafixed,classicalbackground:arigidgrid.Couldthebackgrounditself be quantum? We will touch on this rather topical question [5, 11, 16]. References 1. Arrighi, P., Dowek, G.: The physical church-turing thesis and the principles of quantum theory.Int.J. Found.Comput. Sci. 23(2012) 2. Arrighi, P., Grattage, J.: A quantum game of life. In: Second Symposium on Cellular Automata “Journées Automates Cellulaires” (JAC 2010), Turku, December 2010, TUCS LectureNotes, vol. 13,pp.31–42(2010) 3. Arrighi, P., Grattage, J.: Intrinsically universal n-dimensional quantum cellular automata. J.Comput.Syst. Sci.78,1883–1898(2012) 4. Arrighi, P., Grattage, J.: Partitioned quantum cellular automata are intrinsically universal. Nat. Comput.11, 13–22(2012) 5. Arrighi, P., Martiel, S.: Quantum causal graph dynamics. Phys. Rev. D. 96(2), 024026, (2017).Pre-print, arXiv:1607.06700