On automata networks dynamics: an approach based on computational complexity theory
Professor Advisor
dc.contributor.advisor
Maass Sepúlveda, Alejandro
Professor Advisor
dc.contributor.advisor
Sené, Sylvain
Professor Advisor
dc.contributor.advisor
Goles Chacc, Eric
Professor Advisor
dc.contributor.advisor
Theyssier, Guillaume
Author
dc.contributor.author
Ríos Wilson, Martín Alonso Facundo
Associate professor
dc.contributor.other
Formenti, Enrico
Associate professor
dc.contributor.other
Kari, Jarkko
Associate professor
dc.contributor.other
Rapaport Zimmerman, Iván
Associate professor
dc.contributor.other
Terrier, Veronique
Admission date
dc.date.accessioned
2021-08-27T22:00:17Z
Available date
dc.date.available
2021-08-27T22:00:17Z
Publication date
dc.date.issued
2021
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/181601
General note
dc.description
Tesis para optar al grado de Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática en cotutela con Aix-Marseille Université
es_ES
Abstract
dc.description.abstract
An automata network (AN) is a network of entities, each holding a state from a finite set and related by a graph structure called an \emph{interaction graph}. Each node evolves according to the states of its neighbors in the interaction graph, defining a discrete dynamical system. This thesis work explores two main questions: a) what is the link between dynamical and computational properties of an AN? and b) what is the impact of the interaction graph topology on the global dynamics of an AN?. In order to tackle the first question a notion of computational complexity of an AN family is defined in terms of the computational complexity of decision problems related to the dynamics of the network. On the other hand, the dynamical complexity of a particular AN family is defined in terms of the existence of attractors of exponential period. A strong link between these two last definitions is presented in terms of the notion of simulation between AN families. In this context, complexity is characterized from a localized standpoint by studying the existence of structures called \emph{coherent gadgets} which satisfy two properties: i) they can locally interact in a coherent way as dynamical systems and ii) they are capable of simulating a finite set of functions defined over a fixed finite set. Finally, the second question is addressed in the context of a well-known family called \emph{freezing automata networks}. An AN is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. A general model checking problem capturing many classical decision problems is presented. In addition, when three graph parameters, the maximum degree, the treewidth and the alphabet size are bounded, a fast-parallel algorithm that solves general model checking problem is presented. Moreover, it is shown that the latter problem is unlikely to be fixed-parameter tractable on the treewidth parameter as well as on the alphabet size when considered as single parameters.
es_ES
Patrocinador
dc.description.sponsorship
ANID-BECA DOCTORADO NACIONAL 2018- FOLIO N° 21180910, CMM ANID PIA AFB170001 and ANR project ANR-18-CE40-0002