Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

Gabriel Istrate. Reachability and Recurrence in a Modular Generalization of Annihilating Random Walks (and lights-out games) to hypergraphs. Theoretical Computer Science , 580, pp. 83-93, 2015.

Abstract: We study a discrete asynchronous dynamical system on hypergraphs that can be regarded as a natural extension of annihilating walks along two directions: first, the interaction topology is a hypergraph; second, the number of particles at a vertex of the hypergraph is an element of a finite ring Z_p of integers modulo an odd number p>= 3. Equivalently, particles move on a hypergraph, with a moving particle at a vertex being replaced by one indistinguishable copy at each neighbor in a given hyperedge; particles at a vertex collectively annihilate when their number reaches p.

The boolean version of this system arose in earlier work motivated by our earlier work on the statistical physics of social balance, generalizes certain lights-out games to finite fields and also has some applications to the complexity of local search procedures.

Our result shows that under a liberal sufficient condition on the nature of the interaction hypergraph there exists a polynomial time algorithm (based on linear algebra over Z_p) for deciding reachability and recurrence of this dynamical system. Interestingly, we provide a counterexample that shows that this connection does not extend to all graphs.

For a preprint version see http://tcs.ieat.ro/wp-content/uploads/2013/06/arxiv.pdf

Keywords: discrete complex systems, ights-out games, reachability

URL: http://www.sciencedirect.com/science/article/pii/S0304397515001711

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013