Stably computable predicates are semilinear
From MaRDI portal
Publication:5177291
DOI10.1145/1146381.1146425zbMath1314.68054OpenAlexW2091275311MaRDI QIDQ5177291
David Eisenstat, Dana Angluin, James Aspnes
Publication date: 10 March 2015
Published in: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1146381.1146425
Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Distributed systems (68M14) Network protocols (68M12)
Related Items (48)
Deterministic function computation with chemical reaction networks ⋮ A counter abstraction technique for verifying properties of probabilistic swarm systems ⋮ Population protocols with faulty interactions: the impact of a leader ⋮ Polylogarithmic-Time Leader Election in Population Protocols ⋮ Simple and fast approximate counting and leader election in populations ⋮ The stochastic thermodynamics of computation ⋮ Fast computation by population protocols with a leader ⋮ Recent Advances in Population Protocols ⋮ Information Spreading by Mobile Particles on a Line ⋮ Advances in parameterized verification of population protocols ⋮ Synthesizing and Tuning Chemical Reaction Networks with Specified Behaviours ⋮ Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks ⋮ Speed faults in computation by chemical reaction networks ⋮ Verifying chemical reaction network implementations: a bisimulation approach ⋮ Unnamed Item ⋮ Population protocols: beyond runtime analysis ⋮ The computational power of population protocols ⋮ Unnamed Item ⋮ Simple and Efficient Leader Election ⋮ Passively mobile communicating machines that use restricted space ⋮ Computational models for networks of tiny artifacts: a survey ⋮ Fault-tolerant simulation of population protocols ⋮ Mediated Population Protocols: Leader Election and Applications ⋮ Labelled (Hyper)Graphs, Negotiations and the Naming Problem ⋮ Running time analysis of broadcast consensus protocols ⋮ Position discovery for a system of bouncing robots ⋮ Localization for a system of colliding robots ⋮ Theory of reaction automata: a survey ⋮ A survey of size counting in population protocols ⋮ Verification of population protocols ⋮ How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model ⋮ Leaderless Deterministic Chemical Reaction Networks ⋮ On the number of binary-minded individuals required to compute \(\sqrt {\frac 12}\) ⋮ Mediated population protocols ⋮ Leaderless deterministic chemical reaction networks ⋮ Verifying polymer reaction networks using bisimulation ⋮ Unnamed Item ⋮ Time-space trade-offs in population protocols for the majority problem ⋮ Survivability of bouncing robots ⋮ Towards efficient verification of population protocols ⋮ The computational capability of chemical reaction automata ⋮ Minimal output unstable configurations in chemical reaction networks and deciders ⋮ Probability 1 computation with chemical reaction networks ⋮ Composable computation in discrete chemical reaction networks ⋮ Robustness of Expressivity in Chemical Reaction Networks ⋮ On the convergence of population protocols when population goes to infinity ⋮ On Gossip and Populations ⋮ Space Complexity of Self-stabilizing Leader Election in Passively-Mobile Anonymous Agents
This page was built for publication: Stably computable predicates are semilinear
