Advanced search options

You searched for `subject:( rotor routing)`

. One record found.

▼ Search Limiters

1. Chan, Swee Hong. Nonhalting abelian networks .

Degree: 2019, Cornell University

URL: http://hdl.handle.net/1813/67434

An abelian network is a collection of communicating automata whose state transitions and message passing each satisfy a local commutativity condition. The foundational theory for abelian networks was laid down in a series of papers by Bond and Levine (2016), which mainly focused on networks that halt on all inputs. In this dissertation, we extend the theory of abelian networks to nonhalting networks (i.e., 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 \emph{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 [ ∑_{n ≥ 1} r_{n} z^{n} = \det (\frac{1}{1-z}D - A ) ] where r_{n} 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 (r_{n})_{n ≥ 1} completely determines the spectrum of the simple random walk on the network.
*Advisors/Committee Members: Aguiar, Marcelo (committeeMember), Meszaros, Karola (committeeMember).*

Subjects/Keywords: Critical group; rotor-routing; Mathematics; abelian distributed processors; abelian networks; chip-firing

…are particularly interesting. They include sinkless chip-firing, *rotor*-*routing*, and their… …1.7 Sandpile networks . . . . . . . . . . . . . . . . . . . .
1.8 *Rotor* networks and abelian… …124
7.2 Counting recurrent components . . . . . . . . . . . . . . . . . . . . 135
8 *Rotor*… …abelian networks (specifically *rotor* networks) are used as a way to derandomize models… …invariant: *Rotor* and chip-firing networks on
the same graph have the same P and K, but different…

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Chan, S. H. (2019). Nonhalting abelian networks . (Thesis). Cornell University. Retrieved from http://hdl.handle.net/1813/67434

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Chan, Swee Hong. “Nonhalting abelian networks .” 2019. Thesis, Cornell University. Accessed January 26, 2020. http://hdl.handle.net/1813/67434.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Chan, Swee Hong. “Nonhalting abelian networks .” 2019. Web. 26 Jan 2020.

Vancouver:

Chan SH. Nonhalting abelian networks . [Internet] [Thesis]. Cornell University; 2019. [cited 2020 Jan 26]. Available from: http://hdl.handle.net/1813/67434.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Chan SH. Nonhalting abelian networks . [Thesis]. Cornell University; 2019. Available from: http://hdl.handle.net/1813/67434

Not specified: Masters Thesis or Doctoral Dissertation