|   | 
Details
   web
Records
Author Bitar, N.; Goles, E.; Montealegre, P.
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 Gaspers, S.; Liedloff, M.; Stein, M.; Suchan, K.
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.
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.
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.; Lobos, F.; Montealegre, P.; Ruivo, ELP.; de Oliveira, PPB.
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.
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.
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.; Montalva-Medel, M.; Montealegre, P.; Rios-Wilson, M.
Title On the complexity of generalized Q2R automaton Type
Year 2022 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.
Volume 138 Issue Pages 102355
Keywords Q2R networks; Computational complexity; Limit cycles; P-complete
Abstract We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequential update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is P-Hard.
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 0196-8858 ISBN Medium
Area Expedition Conference
Notes WOS:000830087300008 Approved
Call Number UAI @ alexi.delcanto @ Serial 1610
Permanent link to this record
 

 
Author Goles, E.; Montealegre, P.; Perrot, K.; Theyssier, G.
Title On the complexity of two-dimensional signed majority cellular automata Type
Year 2018 Publication Journal Of Computer And System Sciences Abbreviated Journal J. Comput. Syst. Sci.
Volume 91 Issue Pages 1-32
Keywords Cellular automata dynamics; Majority cellular automata; Signed two-dimensional lattice; Turing universal; Intrinsic universal; Computational complexity
Abstract We study the complexity of signed majority cellular automata on the planar grid. We show that, depending on their symmetry and uniformity, they can simulate different types of logical circuitry under different modes. We use this to establish new bounds on their overall complexity, concretely: the uniform asymmetric and the non-uniform symmetric rules are Turing universal and have a P-complete prediction problem; the non-uniform asymmetric rule is intrinsically universal; no symmetric rule can be intrinsically universal. We also show that the uniform asymmetric rules exhibit cycles of super-polynomial length, whereas symmetric ones are known to have bounded cycle length. (C) 2017 Elsevier Inc. All rights reserved.
Address [Goles, Eric; Montealegre, Pedro] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: p.montealegre@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 0022-0000 ISBN Medium
Area Expedition Conference
Notes WOS:000413130200001 Approved
Call Number UAI @ eduardo.moreno @ Serial 779
Permanent link to this record