UAI Home

FIC-UAI Publication Database

Home |  Show All |  Simple Search |  Advanced Search
Quick Search:
1-20 of 26 records found matching your query:
toggle visibility Search & Display Options
Select All    Deselect All << 1 2 >>
List View
 | 
Citations
 | 
Details
   print
  Records Links
Author Alvarez-Miranda, E.; Pereira, J. doi  openurl
  Title On the complexity of assembly line balancing problems Type
  Year 2019 Publication Computers & Operations Research Abbreviated Journal Comput. Oper. Res.  
  Volume 108 Issue Pages 182-186  
  Keywords Line balancing; Complexity; Bin packing  
  Abstract Assembly line balancing is a family of combinatorial optimization problems that has been widely studied in the literature due to its simplicity and industrial applicability. Most line balancing problems are NP-hard as they subsume the bin packing problem as a special case. Nevertheless, it is common in the line balancing literature to cite [A. Gutjahr and G. Nemhauser, An algorithm for the line balancing problem, Management Science 11 (1964) 308-315] in order to assess the computational complexity of the problem. Such an assessment is not correct since the work of Gutjahr and Nemhauser predates the concept of NP-hardness. This work points at over 50 publications since 1995 with the aforesaid error. (C) 2019 Elsevier Ltd. All rights reserved.  
  Address [Alvarez-Miranda, Eduardo] Univ Talca, Dept Ind Engn, Curico, Chile, Email: jorge.pereira@uai.cl  
  Corporate Author Thesis  
  Publisher Pergamon-Elsevier Science Ltd Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0305-0548 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000471733300014 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 1015  
Permanent link to this record
 
 
Author Araujo, J.; Ducoffe, G.; Nisse, N.; Suchan, K. pdf  doi
openurl 
  Title On interval number in cycle convexity Type
  Year 2018 Publication Discrete Mathematics And Theoretical Computer Science Abbreviated Journal Discret. Math. Theor. Comput. Sci.  
  Volume 20 Issue 1 Pages 35 pp  
  Keywords graph convexity; interval number; domination problems in graphs; complexity and algorithms  
  Abstract Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by in(cc)(G), is the minimum cardinality of a set S subset of V (G) such that every vertex w is an element of E V (G) \ S has two distinct neighbors u, v is an element of S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S. In this work, first we provide bounds on in(cc) (G) and its relations to other graph convexity parameters, and explore its behaviour on grids. Then, we present some hardness results by showing that deciding whetherin(cc) (G) <= k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtain that in(cc) (G) cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = NP). On the positive side, we present polynomial-time algorithms to compute in(cc) (G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q – 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G. Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems.  
  Address [Araujo, Julio] Univ Fed Ceara, Dept Matemat, ParGO, Fortaleza, Ceara, Brazil  
  Corporate Author Thesis  
  Publisher Discrete Mathematics Theoretical Computer Science Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 1462-7264 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000431858800001 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 858  
Permanent link to this record
 
 
Author Becker, F.; Montealegre, P.; Rapaport, I.; Todinca, I. doi  openurl
  Title The role of randomness in the broadcast congested clique model Type
  Year 2021 Publication Information and Computation Abbreviated Journal Inf. Comput.  
  Volume 281 Issue Pages 104669  
  Keywords Distributed computing; Broadcast congested clique; Message size complexity; Private and public coins; Simultaneous multi-party communication  
  Abstract We study the role of randomness in the broadcast congested clique model. This is a message-passing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node.

This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results:

If more than one round is allowed, public randomness is as powerful as private ran-domness.

One-round public-coin algorithms can be exponentially more powerful than determin-istic algorithms running in several rounds.

One-round public-coin algorithms can be exponentially more powerful than one-round private-coin algorithms.

One-round private-coin algorithms can be exponentially more powerful than one-round deterministic algorithms.		  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0890-5401 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000721215200042 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1491  
Permanent link to this record
 
 
Author Bitar, N.; Goles, E.; Montealegre, P. doi  openurl
  Title COMPUTATIONAL COMPLEXITY OF BIASED DIFFUSION-LIMITED AGGREGATION Type
  Year 2022 Publication Siam Journal On Discrete Mathematics Abbreviated Journal SIAM Discret. Math.  
  Volume 36 Issue 1 Pages 823-866  
  Keywords diffusion-limited aggregation; computational complexity; space complexity; NL-completeness; P-completeness  
  Abstract Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by k-DLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of Computational Complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e. all particles of S exactly occupy the positions in P. Our aim is to classify the Prediciton and Realization problems for the different versions of DLA. We first show that Prediction is P-Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case the problem is NL-Complete. With respect to Realization, we show that restricted to 2-DLA the problem is in P, while in the 1-DLA case, the problem is in L.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0895-4801 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000778502000037 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1558  
Permanent link to this record
 
 
Author Dewitte, B.; Concha, E.; Saavedra, D.; Pizarro, O.; Martinez-Villalobos, C.; Gushchina, D.; Ramos, M.; Montecinos, A. doi  openurl
  Title The ENSO-induced South Pacific Meridional Mode Type
  Year 2023 Publication Frontiers in Climate Abbreviated Journal Front. Clim.  
  Volume 4 Issue Pages 18 pp  
  Keywords ENSO; South Pacific Meridional Model; oceanic teleconnection; CMIP; ENSO SO complexity  
  Abstract Previous studies have investigated the role of the Pacific meridional mode (PMM), a climate mode of the mid-latitudes in the Northern and Southern Hemisphere, in favoring the development of the El Niño Southern Oscillation (ENSO). However little is known on how ENSO can influence the development of the PMM. Here we investigate the relationship between ENSO and the South Pacific Meridional Mode (SPMM) focusing on strong SPMM events that follows strong El Niño events. This type of events represents more than 60% of such events in the observational record and the historical simulations of the CESM Large ensemble (CESM-LE). It is first shown that such a relationship is rather stationary in both observations and the CESM-LE. Our analyses further reveal that strong SPMM events are associated with a coastal warming o northern central Chile peaking in Austral winter resulting from the propagation of waves forced at the equator during the development of El Niño events. The time delay between the ENSO peak (Boreal winter) and this coastal warming (Austral winter) can be understood in terms of the diferential contribution of the equatorially-forced propagating baroclinic waves to the warming along

the coast. In particular, the diference in phase speeds of the waves (the

high-order mode the wave the slower) implies that they do not overlap along their propagation south of 20&#9702;S. This contributes to the persistence of warm coastal SST anomalies o Central Chile until the Austral summer following the concurrent El Niño event. This coastal warming is favorable to the development of strong SPMM events as the South Pacific Oscillation become active during that season. The analysis of the simulations of the Coupled Intercomparison Project phases 5 and 6 (CMIP5/6) indicates that very few models realistically simulate this ENSO/SPMM relationship and associated oceanic teleconnection.		  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 2624-9553 ISBN Medium  
  Area Expedition Conference  
  Notes Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1719  
Permanent link to this record
 
 
Author Fomin, F.V.; Golovach, P.A.; Kratochvil, J.; Nisse, N.; Suchan, K. pdf  doi
openurl 
  Title Pursuing a fast robber on a graph Type
  Year 2010 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 411 Issue 7-9 Pages 1167-1181  
  Keywords Pursuit-evasion game on graphs; Cops and Robbers; Complexity; Parameterized complexity; Cliquewidth; Planar graph  
  Abstract The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been Much Studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is W[2]-hard; the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s = 1 but is NP-hard if s = 2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s <= 2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. (C) 2009 Elsevier B.V. All rights reserved.  
  Address [Fomin, Fedor V.; Golovach, Petr A.] Univ Bergen, Dept Informat, N-5020 Bergen, Norway, Email: petr.golovach@durham.ac.uk  
  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:000274886700020 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 83  
Permanent link to this record
 
 
Author Formenti, E.; Goles, E.; Martin, B. pdf  doi
openurl 
  Title Computational Complexity of Avalanches in the Kadanoff Sandpile Model Type
  Year 2012 Publication Fundamenta Informaticae Abbreviated Journal Fundam. Inform.  
  Volume 115 Issue 1 Pages 107-124  
  Keywords Kadanoff Sandpile Model; Bak Sandpile Model; Sandpiles Models; Complexity; Discrete Dynamical Systems; Self-Organized Criticality (SOC)  
  Abstract This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is P-complete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC1 for one-dimensional sandpiles and P-complete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak's model of two-dimensional sandpiles.  
  Address [Formenti, Enrico] Univ Nice Sophia Antipolis, I3S, UMR CNRS 6070, F-06903 Sophia Antipolis, France, Email: enrico.formenti@unice.fr  
  Corporate Author Thesis  
  Publisher Ios Press Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0169-2968 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000302777200008 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 208  
Permanent link to this record
 
 
Author Gajardo, A.; Goles, E. pdf  doi
openurl 
  Title Crossing information in two-dimensional Sandpiles Type
  Year 2006 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 369 Issue 1-3 Pages 463-469  
  Keywords Sandpile; discrete dynamical system; cellular automata; calculability; complexity  
  Abstract We prove that in a two-dimensional Sandpile automaton, embedded in a regular infinite planar cellular space, it is impossible to cross information, if the bit of information is the presence (or absence) of an avalanche. This proves that it is impossible to embed arbitrary logical circuits in a Sandpile through quiescent configurations. Our result applies also for the non-planar neighborhood of Moore. Nevertheless, we also show that it is possible to compute logical circuits with a two-dimensional Sandpile, if a neighborhood of radius two is used in Z(2); crossing information becomes possible in that case, and we conclude that for this neighborhood the Sandpde is P-complete and Turing universal. (c) 2006 Elsevier B.V. All rights reserved.  
  Address Univ Adolfo Ibanez, Santiago, Chile, Email: anahi@ing-mat.udec.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:000242765000035 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 34  
Permanent link to this record
 
 
Author Gaspers, S.; Liedloff, M.; Stein, M.; Suchan, K. pdf  doi
openurl 
  Title Complexity of splits reconstruction for low-degree trees Type
  Year 2015 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.  
  Volume 180 Issue Pages 89-100  
  Keywords Reconstruction of trees; Computational complexity; Computational chemistry  
  Abstract Given a vertex-weighted tree T, the split of an edge em T is the minimum over the weights of the two trees obtained by removing e from T, where the weight of a tree is the sum of weights of its vertices. Given a set of weighted vertices V and a multiset of integers s, we consider the problem of constructing a tree on V whose splits correspond to s. The problem is known to be NP-complete, even when all vertices have unit weight and the maximum vertex degree of T is required to be at most 4. We show that the problem is strongly NP-complete when T is required to be a path, the problem is NP-complete when all vertices have unit weight and the maximum degree of T is required to be at most 3, and it remains NP-complete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3. We also design polynomial time algorithms for the variant where T is required to be a path and the number of distinct vertex weights is constant, and the variant where all vertices have unit weight and T has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but also is a fixed-parameter algorithm for parameter k. Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm. The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong relation between structural invariants of the particles, such as the Wiener index and, less directly, the problem under consideration here, and physico-chemical properties of the substance. (C) 2014 Elsevier B.V. All rights reserved.  
  Address [Gaspers, Serge] Univ New S Wales, Sch Comp Sci & Engn, Sydney, NSW 2052, Australia, Email: sergeg@cse.unsw.edu.au;  
  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 0166-218x ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000346545500009 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 433  
Permanent link to this record
 
 
Author Goles, E.; Montealegre, P. pdf  doi
openurl 
  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. pdf  doi
openurl 
  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. doi  openurl
  Title The complexity of the asynchronous prediction of the majority automata Type
  Year 2020 Publication Information and Computation Abbreviated Journal Inf. Comput.  
  Volume 274 Issue SI Pages  
  Keywords Majority automata; Cellular automata; Prediction problem; Asynchronous updating; Computational complexity; Parallel algorithms; Bootstrap percolation; NP-Completeness  
  Abstract We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a non-zero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the two-dimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NP-Complete.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0890-5401 ISBN Medium  
  Area Expedition Conference  
  Notes Approved  
  Call Number UAI @ eduardo.moreno @ Serial 1124  
Permanent link to this record
 
 
Author Goles, E.; Moreira, A. pdf  url
openurl 
  Title Number-Conserving Cellular Automata and Communication Complexity: A Numerical Exploration Beyond Elementary CAs Type
  Year 2012 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.  
  Volume 7 Issue 2 Pages 151-165  
  Keywords Number-Conserving; Communication Complexity; One-dimensional Cellular Automata  
  Abstract We perform a numerical exploration of number-conserving cellular automata (NCCA) beyond the class of elementary CAs, in search of examples with high communication complexity. We consider some possible generalizations of the elementary rule 184 (a minimal model of traffic, which is the only non-trivial elementary NCCA). as well as the classes of NCCAs which minimally extend either the radius or the state set (with respect to the 2 states and radius 1 of the elementary case). Both for 3 states and radius 1, and for 2 stales and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour.  
  Address [Goles, Eric] Univ Adolfo Ibanez, Santiago, Chile, Email: andres.moreira@usm.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:000302978700004 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 210  
Permanent link to this record
 
 
Author Goles, E.; Palacios, A.G. pdf  doi
openurl 
  Title Dynamical complexity in cognitive neural networks Type
  Year 2007 Publication Biological Research Abbreviated Journal Biol. Res.  
  Volume 40 Issue 4 Pages 479-485  
  Keywords artificial; neural net; brain; dynamical complexity; computational Neurosciences; cellular automata  
  Abstract In the last twenty years an important effort in brain sciences, especially in cognitive science, has been the development of mathematical tool that can deal with the complexity of extensive recordings corresponding to the neuronal activity obtained from hundreds of neurons. We discuss here along with some historical issues, advantages and limitations of Artificial Neural Networks (ANN) that can help to understand how simple brain circuits work and whether ANN can be helpful to understand brain neural complexity.  
  Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl  
  Corporate Author Thesis  
  Publisher Soc Biolgia Chile Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0716-9760 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000256072000009 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 33  
Permanent link to this record
 
 
Author Goles, E.; Adamatzky, A.; Montealegre, P.; Rios-Wilson, M. openurl 
  Title Generating Boolean Functions on Totalistic Automata Networks Type
  Year 2021 Publication International Journal of Unconventional Computing Abbreviated Journal Int. J. Unconv. Comput.  
  Volume 16 Issue 4 Pages 343-391  
  Keywords UNIVERSALITY; PROPAGATION; COMPLEXITY  
  Abstract We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are updated in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 1548-7199 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000654165700002 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1393  
Permanent link to this record
 
 
Author Goles, E.; Guillon, P.; Rapaport, I. pdf  doi
openurl 
  Title Traced communication complexity of cellular automata Type
  Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 412 Issue 30 Pages 3906-3916  
  Keywords Cellular automata; Communication complexity  
  Abstract We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata. (C) 2011 Elsevier B.V. All rights reserved.  
  Address [Guillon, P; Rapaport, I] Univ Chile, DIM CMM, CNRS, UMI 2807, 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:000292589800009 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 152  
Permanent link to this record
 
 
Author Goles, E.; Lobos, F.; Montealegre, P.; Ruivo, ELP.; de Oliveira, PPB. openurl 
  Title Computational Complexity of the Stability Problem for Elementary Cellular Automata Type
  Year 2020 Publication Journal of Cellular Automata Abbreviated Journal J. Cell. Autom.  
  Volume 15 Issue 4 Pages 261-304  
  Keywords One-dimensional cellular automata; elementary cellular automata; computational complexity; stability problem; decision problem  
  Abstract Given an elementary cellular automaton and a cell v, we define the stability decision problem as the determination of whether or not the state of cell v will ever change, at least once, during the time evolution of the rule, over a finite input configuration. Here, we perform the study of the entire elementary cellular automata rule space, for the two possible decision cases of the problem, namely, changes in v from state 0 to 1 (0 -> 1), and the other way round (1 -> 0). Out of the 256 elementary cellular automata, we show that for all of them, at least one of the two decision problems is in the NC complexity class.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language 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:000613086900002 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1329  
Permanent link to this record
 
 
Author Goles, E.; Maldonado, D.; Montealegre, P. doi  openurl
  Title On the complexity of asynchronous freezing cellular automata Type
  Year 2021 Publication Information and Computation Abbreviated Journal Inf. Comput.  
  Volume 281 Issue Pages 104764  
  Keywords Cellular automata; Computational complexity; Freezing dynamics  
  Abstract In this paper we study the family of freezing cellular automata (FCA) in the context of asynchronous updating schemes. A cellular automaton is called freezing if there exists an order of its states, and the transitions are only allowed to go from a lower to a higher state. A cellular automaton is asynchronous if at each time-step only one cell is updated. We define the problem ASYNCUNSTABILITY, which consists in deciding there exists a sequential updating scheme that changes the state of a given cell.

We begin showing that ASYNCUNSTABILITY is in NL for any one-dimensional FCA. Then we focus on the family of life-like freezing CA (LFCA). We study the complexity of ASYNCUNSTABILITY for all LFCA in the triangular and square grids, showing that almost all of them can be solved in NC, except for one rule for which the problem is NP-Complete. (C) 2021 Elsevier Inc. All rights reserved.		  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0890-5401 ISBN Medium  
  Area 0890-5401 Expedition Conference  
  Notes WOS:000721215200020 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1490  
Permanent link to this record
 
 
Author Goles, E.; Maldonado, D.; Montealegre, P.; Ollinger, N. doi  openurl
  Title On the complexity of the stability problem of binary freezing totalistic cellular automata Type
  Year 2020 Publication Information And Computation Abbreviated Journal Inf. Comput.  
  Volume 274 Issue Pages 21 pp  
  Keywords Cellular automata; Computational complexity; Freezing cellular automata; Totalistic cellular automata; Fast parallel algorithms; P-Complete  
  Abstract In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the STABILITY problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that: For Algebraic and Topological Rules the STABILITY problem is in NC. For Turing Universal rules the STABILITY problem is P-Complete. (C) 2020 Elsevier Inc. All rights reserved.  
  Address [Goles, Eric; Montealegre, Pedro] Univ Adolfo Ibanez, Fac Ingn & Ciencias, 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 0890-5401 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000573267700008 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1238  
Permanent link to this record
 
 
Author Goles, E.; Meunier, P.E.; Rapaport, I.; Theyssier, G. pdf  doi
openurl 
  Title Communication complexity and intrinsic universality in cellular automata Type
  Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 412 Issue 1-2 Pages 2-21  
  Keywords Cellular automata; Communication complexity; Intrinsic universality  
  Abstract The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be “universal”, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space-time rescaling and it is intrinsic to the model of cellular automata. intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal. (C) 2010 Elsevier B.V. All rights reserved.  
  Address [Meunier, P. -E.; Theyssier, G.] Univ Savoie, CNRS, LAMA, F-73376 Le Bourget Du Lac, France, Email: guillaume.theyssier@univ-savoie.fr  
  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:000285952400002 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 118  
Permanent link to this record
Select All    Deselect All << 1 2 >>
List View
 | 
Citations
 | 
Details
   print
toggle visibility
Save Citations:
Export Records:
Home CQL Search  |  Library Search  |  Show Record  |  Extract Citations Help