|
|
Goles, E., & Montealegre, P. (2014). Computational complexity of threshold automata networks under different updating schemes. Theor. Comput. Sci., 559, 3–19.
Abstract: Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND-OR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.
|
|
|
|
Goles, E., & Montealegre, P. (2015). The complexity of the majority rule on planar graphs. Adv. Appl. Math., 64, 111–123.
Abstract: We study the complexity of the majority rule on planar automata networks. We reduce a special case of the Monotone Circuit Value Problem to the prediction problem of determining if a vertex of a planar graph will change its state when the network is updated with the majority rule. (C) 2014 Elsevier Inc. All rights reserved.
|
|
|
|
Goles, E., Montealegre, P., & Vera, J. (2016). Naming Game Automata Networks. J. Cell. Autom., 11(5-6), 497–521.
Abstract: In this paper we introduce automata networks to model some features of the emergence of a vocabulary related with the naming game model. We study the dynamical behaviour (attractors and convergence) of extremal and majority local functions.
|
|
|
|
Leal, L., Montealegre, P., Osses, A., & Rapaport, I. (2022). A large diffusion and small amplification dynamics for density classification on graphs. Int. J. Mod Phys. C, Early Access.
Abstract: The density classification problem on graphs consists in finding a local dynamics such that, given a graph and an initial configuration of 0's and 1's assigned to the nodes of the graph, the dynamics converge to the fixed point configuration of all 1's if the fraction of 1's is greater than the critical density (typically 1/2) and, otherwise, it converges to the all 0's fixed point configuration. To solve this problem, we follow the idea proposed in [R. Briceno, P. M. de Espanes, A. Osses and I. Rapaport, Physica D 261, 70 (2013)], where the authors designed a cellular automaton inspired by two mechanisms: diffusion and amplification. We apply this approach to different well-known graph classes: complete, regular, star, Erdos-Renyi and Barabasi-Albert graphs.
|
|
|
|
Vera, J. (2017). Self-Organization of Vocabularies under Different Interaction Orders. Artif. Life, 23(2), 287–294.
Abstract: Traditionally, the formation of vocabularies has been studied by agent-based models (primarily, the naming game) in which random pairs of agents negotiate word-meaning associations at each discrete time step. This article proposes a first approximation to a novel question: To what extent is the negotiation of word-meaning associations influenced by the order in which agents interact? Automata networks provide the adequate mathematical framework to explore this question. Computer simulations suggest that on two-dimensional lattices the typical features of the formation of word-meaning associations are recovered under random schemes that update small fractions of the population at the same time; by contrast, if larger subsets of the population are updated, a periodic behavior may appear.
|
|
|
|
Vera, J., & Goles, E. (2016). Automata Networks for Memory Loss Effects in the Formation of Linguistic Conventions. Cogn. Comput., 8(3), 462–466.
Abstract: This work attempts to give new theoretical insights into the absence of intermediate stages in the evolution of language. In particular, a mathematical model, based on automata networks, is proposed with the purpose to answer a crucial question: How a population of language users can reach agreement on linguistic conventions? To describe the appearance of drastic transitions in the development of language, an extremely simple model of working memory is adopted: at each time step, language users simply lose part of their word memories according to a forgetfulness parameter. Through computer simulations on low-dimensional lattices, sharp transitions at critical values of the parameter are described.
|
|
