No CrossRef data available.
Article contents
Abelian Logic Gates
Published online by Cambridge University Press: 13 March 2019
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2019
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
[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
You have
Access
- 1
- Cited by