{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:57:42Z","timestamp":1775840262237,"version":"3.50.1"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,5]]},"abstract":"<jats:p>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 <jats:italic>toppler<\/jats:italic>, 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 <jats:italic>adder<\/jats:italic> gate, which simply combines two streams of particles, each of our gates has only one input wire, which sends letters (\u2018particles\u2019) 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 \u2115<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup> to \u2115<jats:sup>\u2113<\/jats:sup> 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.<\/jats:p>","DOI":"10.1017\/s0963548318000482","type":"journal-article","created":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T04:34:47Z","timestamp":1552451687000},"page":"388-422","source":"Crossref","is-referenced-by-count":1,"title":["Abelian Logic Gates"],"prefix":"10.1017","volume":"28","author":[{"given":"ALEXANDER E.","family":"HOLROYD","sequence":"first","affiliation":[]},{"given":"LIONEL","family":"LEVINE","sequence":"additional","affiliation":[]},{"given":"PETER","family":"WINKLER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,3,13]]},"reference":[{"key":"S0963548318000482_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/0401039"},{"key":"S0963548318000482_ref22","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004524500416"},{"key":"S0963548318000482_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2009.09.023"},{"key":"S0963548318000482_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s11118-008-9104-6"},{"key":"S0963548318000482_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.04.030"},{"key":"S0963548318000482_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7643-8786-0_17"},{"key":"S0963548318000482_ref12","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/12952"},{"key":"S0963548318000482_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-015-0266-9"},{"key":"S0963548318000482_ref10","first-page":"95","article-title":"A growth model, a game, an algebra, Lagrange inversion, and characteristic classes","volume":"49","author":"Diaconis","year":"1991","journal-title":"Rend. Sem. Mat. Univ. Pol. Torino,"},{"key":"S0963548318000482_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-009-9899-6"},{"key":"S0963548318000482_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2006.04.004"},{"key":"S0963548318000482_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(02)01426-7"},{"key":"S0963548318000482_ref7","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.64.1613"},{"key":"S0963548318000482_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20412"},{"key":"S0963548318000482_ref5","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnu025"},{"key":"S0963548318000482_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1030984"},{"key":"S0963548318000482_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.02.029"},{"key":"S0963548318000482_ref11","doi-asserted-by":"publisher","DOI":"10.2307\/2370405"},{"key":"S0963548318000482_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-015-0648-4"},{"key":"S0963548318000482_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(98)00493-2"},{"key":"S0963548318000482_ref6","unstructured":"Cori R. and Le Borgne Y. (2013) The Riemann\u2013Roch theorem for graphs and the rank in complete graphs. arXiv:1308.5325"},{"key":"S0963548318000482_ref17","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/13498"},{"key":"S0963548318000482_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00029-015-0192-z"},{"key":"S0963548318000482_ref16","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/520\/10256"},{"key":"S0963548318000482_ref25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.021107"},{"key":"S0963548318000482_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091964"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T19:38:20Z","timestamp":1555011500000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000482\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,13]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["S0963548318000482"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000482","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,13]]}}}