Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-24T13:01:09.371Z Has data issue: false hasContentIssue false
  • English
  • Français

Abelian Logic Gates

Part of: Theory of computing Operations research and management science

Published online by Cambridge University Press:  13 March 2019

ALEXANDER E. HOLROYD ,
LIONEL LEVINE  and
PETER WINKLER
ALEXANDER E. HOLROYD
Affiliation:
University of Washington, Seattle, WA 98195, USAhttp://aeholroyd.org
LIONEL LEVINE
Affiliation:
Cornell University, Ithaca, NY 14853, USAhttp://www.math.cornell.edu/~levine
PETER WINKLER
Affiliation:
Dartmouth College, Hanover, NH 03755, USAhttp://math.dartmouth.edu/~pw
Get access Rights & Permissions [Opens in a new window]

Abstract

An abelian processor is an automaton whose output is independent of the order of its inputs. Bond and Levine have proved that a network of abelian processors performs the same computation regardless of processing order (subject only to a halting condition). We prove that any finite abelian processor can be emulated by a network of certain very simple abelian processors, which we call gates. The most fundamental gate is a toppler, which absorbs input particles until their number exceeds some given threshold, at which point it topples, emitting one particle and returning to its initial state. With the exception of an adder gate, which simply combines two streams of particles, each of our gates has only one input wire, which sends letters (‘particles’) from a unary alphabet. Our results can be reformulated in terms of the functions computed by processors, and one consequence is that any increasing function from ℕk to ℕℓ that is the sum of a linear function and a periodic function can be expressed in terms of (possibly nested) sums of floors of quotients by integers.

MSC classification

Primary: 68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Secondary: 68Q45: Formal languages and automata 68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) 90B10: Network models, deterministic
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 3 , May 2019 , pp. 388 - 422
Copyright
Copyright © Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

The second author is supported by NSF grant DMS-1455272 and a Sloan Fellowship.

‡

The third author is supported by NSF grant DMS-1162172.

References

[1] Bond, B. and Levine, L. (2016) Abelian networks I: Foundations and examples. SIAM J. Discrete Math. 30 856–874.Google Scholar
[2] Bond, B. and Levine, L. (2016) Abelian networks II: Halting on all inputs. Selecta Math. 22 319–340.Google Scholar
[3] Bond, B. and Levine, L. (2016) Abelian networks III: The critical group. J. Alg. Combin. 43 635–663.Google Scholar
[4] Cairns, H. (2018) “Some halting problems for abelian sandpiles are undecidable in dimension three.” SIAM Journal on Discrete Mathematics 32.4 2636–2666.Google Scholar
[5] Chan, M., Church, T. and Grochow, J. A. (2015) Rotor-routing and spanning trees on planar graphs. Int. Math. Res. Not. 2015 3225–3244.Google Scholar
[6] Cori, R. and Le Borgne, Y. (2013) The Riemann–Roch theorem for graphs and the rank in complete graphs. arXiv:1308.5325Google Scholar
[7] Dhar, D. (1990) Self-organized critical state of sandpile automaton models. Phys. Rev. Lett. 64 1613–1616.Google Scholar
[8] Dhar, D. (1999) The abelian sandpile and related models. Physica A 263 4–25.Google Scholar
[9] Dhar, D. (2006) Theoretical studies of self-organized criticality. Physica A 369 29–70.Google Scholar
[10] Diaconis, P. and Fulton, W. (1991) A growth model, a game, an algebra, Lagrange inversion, and characteristic classes. Rend. Sem. Mat. Univ. Pol. Torino, 49 95–119.Google Scholar
[11] Dickson, L. E. (1913) Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Amer. J. Math 35 413–422.Google Scholar
[12] Farrell, M. and Levine, L. (2016) CoEulerian graphs. Proc. Amer. Math. Soc. 144 2847–2860.Google Scholar
[13] Fey, A., Levine, L. and Peres, Y. (2010) Growth rates and explosions in sandpiles. J. Statist. Phys. 138 143–159.Google Scholar
[14] Friedrich, T. and Levine, L. (2013) Fast simulation of large-scale growth models. Random Struct. Alg. 42 185–213.Google Scholar
[15] Holroyd, A. E., Levine, L., Mészáros, K., Peres, Y., Propp, J. and Wilson, D. B. (2008) Chip-firing and rotor-routing on directed graphs. In In and Out of Equilibrium 2, Vol. 60 of Progress in Probability, Birkhäuser, pp. 331–364.Google Scholar
[16] Holroyd, A. E. and Propp, J. G. (2010) Rotor walks and Markov chains. In Algorithmic Probability and Combinatorics, Vol. 520 of Contemporary Mathematics, American Mathematical Society, pp. 105–126.Google Scholar
[17] Hujter, B., Kiss, V. and Tóthmérész, L. (2017) On the complexity of the chip-firing reachability problem. Proc. Amer. Math. Soc. 145 3343–3356.Google Scholar
[18] Kiss, V. and Tóthmérész, L. (2015) Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph. Discrete Appl. Math. 193 48–56.Google Scholar
[19] Levine, L. and Peres, Y. (2009) Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile. Potential Anal. 30 1–27.Google Scholar
[20] Mejía, C. and Montoya, J. A. (2011) On the complexity of sandpile critical avalanches. Theoret. Comput. Sci. 412 3964–3974.Google Scholar
[21] Montoya, J. A. and Mejía, C. (2009) On the complexity of sandpile prediction problems. Electron. Notes Theoret. Comput. Sci. 252 229–245.Google Scholar
[22] Moore, C. and Nilsson, M. (1999) The computational complexity of sandpiles. J. Statist. Phys. 96 205–224.Google Scholar
[23] Ostojic, S. (2003) Patterns formed by addition of grains to only one site of an abelian sandpile. Physica A 318 187–199.Google Scholar
[24] Perrot, K. and Van Pham, Trung (2015) Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs. Ann. Combin. 19 373–396.Google Scholar
[25] Sadhu, T. and Dhar, D. (2012) Pattern formation in fast-growing sandpiles. Phys. Rev. E 85 021107.Google Scholar
[26] Tardos, G. (1988) Polynomial bound for a chip firing game on graphs. SIAM J. Discrete Math. 1 397–398.Google Scholar