Abelian logic gates

DOI10.1017/S0963548318000482MaRDI QIDQ5222545zbMATH OpenOpenAlexWikidataFDO

Authors A. E. Holroyd, Lionel Levine, Peter Winkler

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.00422

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Networks and circuits as models of computation; circuit complexity (68Q06)

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. Our results can be reformulated in terms of the functions computed by processors, and one consequence is that any increasing function from N^k to N^l 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.

Recommendations

• Abelian networks. I: Foundations and examples
• scientific article; zbMATH DE number 56705
• Abelian networks. II: Halting on all inputs
• The Parallel Complexity of Abelian Permutation Group Problems
• Abelian networks IV. Dynamics of nonhalting networks

Cites work

• scientific article; zbMATH DE number 218327 (Why is no real title available?)
• Abelian networks. I: Foundations and examples
• Abelian networks. II: Halting on all inputs
• Abelian networks. III: The critical group
• Chip-Firing and Rotor-Routing on Directed Graphs
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• CoEulerian graphs
• Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
• Growth rates and explosions in sandpiles
• On the complexity of sandpile critical avalanches
• On the complexity of sandpile prediction problems
• On the complexity of the chip-firing reachability problem
• On the ranks of configurations on the complete graph
• Pattern formation in growing sandpiles with multiple sources or sinks
• Patterns formed by addition of grains to only one site of an Abelian sandpile
• Polynomial Bound for a Chip Firing Game on Graphs
• Rotor walks and Markov chains
• Rotor-routing and spanning trees on planar graphs
• Self-organized critical state of sandpile automaton models
• Some halting problems for abelian sandpiles are undecidable in dimension three
• Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile
• The computational complexity of sandpiles

Cited in

(10)

• Elementary gates for cartoon computation
• Abelian networks IV. Dynamics of nonhalting networks
• Few Product Gates But Many Zeros
• Interference-based logic gates
• scientific article; zbMATH DE number 4135919 (Why is no real title available?)
• Abelian networks. II: Halting on all inputs
• scientific article; zbMATH DE number 6292740 (Why is no real title available?)
• Sorting via chip-firing
• Abelian networks. I: Foundations and examples
• Sorting via chip-firing

This page was built for publication: Abelian logic gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222545)