|   | 
Details
   web
Records
Author Goles, E.; Montealegre, P.
Title Computational complexity of threshold automata networks under different updating schemes Type
Year 2014 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 559 Issue Pages 3-19
Keywords Automata networks; Threshold functions; Computational complexity; Updating scheme; P-completeness; NC; NP-Hard
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.
Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias & Tecnol, Santiago, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0304-3975 ISBN Medium
Area Expedition Conference
Notes WOS:000347025300002 Approved
Call Number UAI @ eduardo.moreno @ Serial 434
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P.
Title The complexity of the majority rule on planar graphs Type
Year 2015 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.
Volume 64 Issue Pages 111-123
Keywords Automata networks; Computational complexity; Majority; P-Completeness; NC; Planar graph
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.
Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias & Tecnol, Santiago, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Academic Press Inc Elsevier Science Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0196-8858 ISBN Medium
Area Expedition Conference
Notes WOS:000348883400007 Approved
Call Number UAI @ eduardo.moreno @ Serial 445
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P.; Vera, J.
Title Naming Game Automata Networks Type
Year 2016 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.
Volume 11 Issue 5-6 Pages 497-521
Keywords Automata networks; cellular automata; majority functions; energy operator; naming game; fixed points; limit cycles
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.
Address [Goles, Eric; Vera, Javier] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Avda Diagonal Las Torres 2640, Santiago, Chile, Email: eric.chacc@uai.cl;
Corporate Author Thesis
Publisher Old City Publishing Inc Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1557-5969 ISBN Medium
Area Expedition Conference
Notes WOS:000382426500007 Approved
Call Number UAI @ eduardo.moreno @ Serial 649
Permanent link to this record
 

 
Author Vera, J.
Title Self-Organization of Vocabularies under Different Interaction Orders Type
Year 2017 Publication Artificial Life Abbreviated Journal Artif. Life
Volume 23 Issue 2 Pages 287-294
Keywords Vocabulary; automata networks; interaction orders; naming game
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.
Address [Vera, Javier] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Avda Diagonal Las Torres 2640, Santiago, Chile, Email: jxvera@gmail.com
Corporate Author Thesis
Publisher Mit Press Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1064-5462 ISBN Medium
Area Expedition Conference
Notes WOS:000402704800008 Approved
Call Number UAI @ eduardo.moreno @ Serial 738
Permanent link to this record
 

 
Author Vera, J.; Goles, E.
Title Automata Networks for Memory Loss Effects in the Formation of Linguistic Conventions Type
Year 2016 Publication Cognitive Computation Abbreviated Journal Cogn. Comput.
Volume 8 Issue 3 Pages 462-466
Keywords Automata networks; Linguistic conventions; Working memory; Sharp transition
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.
Address [Vera, Javier; Goles, Eric] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Avda Diagonal Torres 2640, Santiago, Chile, Email: jxvera@gmail.com;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1866-9956 ISBN Medium
Area Expedition Conference
Notes WOS:000376284900006 Approved
Call Number UAI @ eduardo.moreno @ Serial 625
Permanent link to this record