Resumen de Parallel Dynamical Systens Over Graphs.
Silvia Martínez Sanhauja 
It is beyond dispute that to find ways to apply ideas from Mathematics to Computation is a compelling need. In this sense, the development of the theory of Computation is one of the most important tasks in modern Mathematics. In fact, several mathematical concepts have been revealed as fundamental in order to establish this theory of Computation. In this thesis, Boolean algebras, graphs and discrete dynamical systems are mixed properly to construct a mathematical model, named parallel dynamical system (PDS) that allows us to formalize and analyze computational processes, thus contributing to the development of the theory of Computation. In computer processes, there are many entities and each entity has a state at a given time, usually ON/OFF. Thus, it is natural to consider that its state can be modelled by the basic Boolean algebra {0,1}. The update of the states of these entities constitutes an evolution in time of the system, that is, a discrete dynamical system. The evolution of the system depends on the relations among entities, which are usually represented by a graph which is called the dependency graph of the system, and on local functions, each of them acting on the state of an entity and the states of the entities related to it. If the states of the entities are updated in a parallel (or synchronous) manner, the system is called parallel dynamical system (PDS), while if they are updated in a sequential (or asynchronous) order, the system is named sequential dynamical system (SDS). Our main goal in this thesis is to give a complete characterization of the orbit structure for the case of PDS over undirected graphs and essential properties for PDS over directed graphs. Since computational studies become inefficient when the number of entities is big enough, the unique way to give general results for these systems is to find out their properties analytically, as done in this work in Chapters 2, 3 and 4 in order to describe the different coexistent periodic orbits of PDS. Firstly, we generalize some known results, giving a complete characterization of the orbit structure of PDS over undirected dependency graphs, with maxterms and minterms Boolean functions as global evolution operators. Secondly, we obtain essential properties of the orbit structure of PDS over directed dependency graphs (PDDS). In this sense, for PDDS on general maxterms and minterms, it is shown that the situation becomes more involved, since any periodic orbit can appear, so breaking the pattern found for the undirected case, where only fixed points or 2-periodic orbits can exist. We also demonstrate that this breakdown is due to the existence of directed cycles in the directed dependency graph, while for PDDS over acyclic directed dependency graphs the periodic orbits continue being only fixed points or 2-periodic ones. After that, we proposed and analyzed in detail two extensions of PDS. ¿ On one hand, we extend the manner of defining the evolution update of these systems, without limiting the local functions to be dependent restrictions of a global one. Concretely, we analyze the cases concerned with the AND, OR, NAND and NOR functions as independent local functions over undirected and also directed dependency graphs. This extension allows us to show a richer dynamics in these new kinds of PDS. ¿ On the other hand, we introduce another wide generalization by considering that the states of the entities can take values in an arbitrary Boolean algebra. This definition widely extends the traditional one, where it is assumed that every entity can take values in the simplest Boolean algebra {0, 1}. Finally, since the coexistence of periodic orbits depends on the number of entities, their connections and the Boolean operator, analytical results cannot be given in general. In view of this, we develop several matrix methods for the computation of orbits in these systems. These algorithms constitute a new tool for the study of orbits of PDS. Moreover, we extend these methods to the case of SDS, even when the local functions are locally independent.
