Abelian Networks IV. Dynamics of Nonhalting Networks
Seiten
2022
American Mathematical Society (Verlag)
978-1-4704-5141-7 (ISBN)
American Mathematical Society (Verlag)
978-1-4704-5141-7 (ISBN)
A nonhalting abelian network can be realised as a discrete dynamical system in many different ways, depending on the update order. The authors show that certain features of the dynamics, such as minimal period length, have intrinsic definitions that do not require specifying an update order.
An abelian network is a collection of communicating automata whose state transitions and message passing each satisfy a local commutativity condition. This paper is a continuation of the abelian networks series of Bond and Levine (2016), for which we extend thetheory of abelian networks that halt on all inputs to networks that can run forever. A nonhalting abelian network can be realized as a discrete dynamical system in many different ways, depending on the update order. We show that certain features of the dynamics, such as minimal period length, have intrinsic definitions that do not require specifying an update order.
We give an intrinsic definition of the torsion group of a finite irreducible (halting or nonhalting) abelian network, and show that it coincides with the critical group of Bond and Levine (2016) if the network is halting. We show that the torsion group acts freely on the set of invertible recurrent components of the trajectory digraph, and identify when this action is transitive. This perspective leads to new results even in the classical case of sinkless rotor networks (deterministic analogues of random walks). In Holroyd et. al (2008) it was shown that the recurrent configurations of a sinkless rotor network with just one chip are precisely the unicycles (spanning subgraphs with a unique oriented cycle, with the chip on the cycle). We generalize this result to abelian mobile agent networks with any number of chips. We give formulas for generating series such as rnzn =det( 1 n?1 1 ?zD?A) where rn is the number of recurrent chip-and-rotor configurations with n chips; D is the diagonal matrix of outdegrees, and A is the adjacency matrix. A consequence is that the sequence (rn)n?1 completely determines the spectrum of the simple random walk on the network.
An abelian network is a collection of communicating automata whose state transitions and message passing each satisfy a local commutativity condition. This paper is a continuation of the abelian networks series of Bond and Levine (2016), for which we extend thetheory of abelian networks that halt on all inputs to networks that can run forever. A nonhalting abelian network can be realized as a discrete dynamical system in many different ways, depending on the update order. We show that certain features of the dynamics, such as minimal period length, have intrinsic definitions that do not require specifying an update order.
We give an intrinsic definition of the torsion group of a finite irreducible (halting or nonhalting) abelian network, and show that it coincides with the critical group of Bond and Levine (2016) if the network is halting. We show that the torsion group acts freely on the set of invertible recurrent components of the trajectory digraph, and identify when this action is transitive. This perspective leads to new results even in the classical case of sinkless rotor networks (deterministic analogues of random walks). In Holroyd et. al (2008) it was shown that the recurrent configurations of a sinkless rotor network with just one chip are precisely the unicycles (spanning subgraphs with a unique oriented cycle, with the chip on the cycle). We generalize this result to abelian mobile agent networks with any number of chips. We give formulas for generating series such as rnzn =det( 1 n?1 1 ?zD?A) where rn is the number of recurrent chip-and-rotor configurations with n chips; D is the diagonal matrix of outdegrees, and A is the adjacency matrix. A consequence is that the sequence (rn)n?1 completely determines the spectrum of the simple random walk on the network.
Swee Hong Chan, Cornell University, Ithaca, New York. Lionel Levine, Cornell University, Ithaca, New York.
| Erscheinungsdatum | 31.05.2022 |
|---|---|
| Reihe/Serie | Memoirs of the American Mathematical Society |
| Verlagsort | Providence |
| Sprache | englisch |
| Maße | 178 x 254 mm |
| Gewicht | 197 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Angewandte Mathematik |
| ISBN-10 | 1-4704-5141-7 / 1470451417 |
| ISBN-13 | 978-1-4704-5141-7 / 9781470451417 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Buch | Softcover (2025)
Springer Vieweg (Verlag)
CHF 62,95
Buch | Softcover (2025)
Springer Fachmedien Wiesbaden (Verlag)
CHF 69,95
Buch | Softcover (2024)
Springer Vieweg (Verlag)
CHF 53,15
