|   | 
Details
   web
Records
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
 

 
Author Golovach, P.A.; Heggernes, P.; Lima, P.T.; Montealegre, P.
Title Finding connected secluded subgraphs Type
Year 2020 Publication Journal Of Computer And System Sciences Abbreviated Journal J. Comput. Syst. Sci.
Volume 113 Issue Pages 101-124
Keywords Secluded subgraph; Parameterized complexity; Forbidden subgraphs
Abstract Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. However, for many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the SECLUDED Pi-SUBGRAPH problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Pi, even when parameterized by k + t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Pi. In particular, we show that the CONNECTED SECLUDED Pi-SUBGRAPH problem is FPT when parameterized by just t for many important graph properties Pi. (C) 2020 Elsevier Inc. All rights reserved.
Address [Golovach, Petr A.; Heggernes, Pinar; Lima, Paloma T.] Univ Bergen, Dept Informat, N-5020 Bergen, Norway, Email: petr.golovach@uib.no;
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:000539435200006 Approved
Call Number UAI @ eduardo.moreno @ Serial 1191
Permanent link to this record
 

 
Author Gutierrez, C.; Hurtado, C.A.; Mendelzon, A.O.; Perez, J.
Title Foundations of Semantic Web databases Type
Year 2011 Publication Journal Of Computer And System Sciences Abbreviated Journal J. Comput. Syst. Sci.
Volume 77 Issue 3 Pages 520-541
Keywords Semantic Web; RDF model; Query language
Abstract The Semantic Web is based on the idea of a common and minimal language to enable large quantities of existing data to be analyzed and processed. This triggers the need to develop the database foundations of this basic language, which is the Resource Description Framework (RDF). This paper addresses this challenge by: 1) developing an abstract model and query language suitable to formalize and prove properties about the RDF data and query language; 2) studying the RDF data model, minimal and maximal representations, as well as normal forms; 3) studying systematically the complexity of entailment in the model, and proving complexity bounds for the main problems; 4) studying the notions of query answering and containment arising in the RDF data model; and 5) proving complexity bounds for query answering and query containment. (C) 2010 Elsevier Inc. All rights reserved.
Address [Gutierrez, Claudio] Univ Chile, Dept Comp Sci, Santiago, Chile, Email: cgutierr@dcc.uchile.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:000288474800006 Approved
Call Number UAI @ eduardo.moreno @ Serial 129
Permanent link to this record
 

 
Author Montealegre, R.; Perez-Salazar, S.; Rapaport, I.; Todinca, I.
Title Graph reconstruction in the congested clique Type
Year 2020 Publication Journal Of Computer And System Sciences Abbreviated Journal J. Comput. Syst. Sci.
Volume 113 Issue Pages 1-17
Keywords Distributed computing; Congested clique; Round complexity; Reconstruction problem; Graph classes
Abstract In this paper we study the reconstruction problem in the congested clique model. Given a class of graphs g, the problem is defined as follows: if G is not an element of g, then every node must reject; if G is an element of g, then every node must end up knowing all the edges of G. The cost of an algorithm is the total number of bits received by any node through one link. It is not difficult to see that the cost of any algorithm that solves this problem is Omega(log vertical bar g(n)vertical bar/n), where g(n) is the subclass of all n-node labeled graphs in g. We prove that the lower bound is tight and that it is possible to achieve it with only 2 rounds. (C) 2020 Elsevier Inc. All rights reserved.
Address [Montealegre, R.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: p.montealegre@edu.uai;
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:000539435200001 Approved
Call Number UAI @ eduardo.moreno @ Serial 1190
Permanent link to this record