Stably computable predicates are semilinear

D. Angluin,J. Aspnes,David Eisenstat

Published 2006 in ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

ABSTRACT

No abstract is available for this paper.

PUBLICATION RECORD

Publication year
2006
Venue
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
Publication date
2006-07-23
Fields of study
Mathematics, Computer Science
Identifiers
DOI 10.1145/1146381.1146425
External record
Open on Semantic Scholar
Source metadata
Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

No claims are published for this paper.

CONCEPTS

No concepts are published for this paper.

REFERENCES

Convex Sets and their Applications
2006influential reference
On the Power of Anonymous One-Way Communication
2005cited by this paper
Stably Computable Properties of Network Graphs
2005cited by this paper
Computation in networks of passively mobile finite-state sensors
2004cited by this paper
Catalytic P systems, semilinear sets, and vector addition systems
2004cited by this paper
Convex Sets and Their Applications
1982cited by this paper
On the Reachability Problem for 5-Dimensional Vector Addition Systems
1976cited by this paper
Ordering by Divisibility in Abstract Algebras
1952cited by this paper

CITED BY

Speaking of Opinions: Comparing Approaches to Modelling Opinion Manipulation
2026cites this paper
Robust predicate and function computation in continuous chemical reaction networks
2025cites this paper
A Coupled Reconfiguration Mechanism That Enables Powerful, Pseudoknot-Robust DNA Strand Displacement Devices with 2-Stranded Inputs
2025cites this paper
Enhancing reliability of composed non-output-oblivious chemical reaction networks
2024cites this paper
Complete Graph Identification in Population Protocols
2024cites this paper
Optimal Information Encoding in Chemical Reaction Networks
2023cites this paper
A Coupled Reconfiguration Mechanism for Single-Stranded DNA Strand Displacement Systems
2022cites this paper
A counter abstraction technique for verifying properties of probabilistic swarm systems
2022cites this paper
On the Computational Power of Phosphate Transfer Reaction Networks
2022influential citation
A survey of size counting in population protocols
2021cites this paper
Theory of reaction automata: a survey
2021cites this paper
Revisiting thermodynamics in computation and information theory
2021cites this paper
Running Time Analysis of Broadcast Consensus Protocols
2021influential citation
Fast Graphical Population Protocols
2021cites this paper
Simple and fast approximate counting and leader election in populations
2021cites this paper
Rate-independent Computation in Continuous Chemical Reaction Networks
2021influential citation
State Complexity of Protocols with Leaders
2021influential citation
Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem
2021cites this paper
Population Protocols: Beyond Runtime Analysis
2021influential citation
Distributed Population Protocols: Naturally!
2021cites this paper
Self-Stabilizing Phase Clocks and the Adaptive Majority Problem
2021cites this paper
Brief Announcement: A Time and Space Optimal Stable Population Protocol Solving Exact Majority
2021cites this paper
When Wireless Crowd Charging Meets Online Social Networks: A Vision for Socially Motivated Energy Sharing
2020cites this paper
A Novel Framework for Capacity Analysis of Diffusion-Based Molecular Communication Incorporating Chemical Reactions
2020cites this paper
Simulating Population Protocols in Sub-Constant Time per Interaction
2020cites this paper
Population Protocols: Expressiveness, Succinctness and Automatic Verification
2020cites this paper
LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS
2020influential citation
Composable Computation in Leaderless, Discrete Chemical Reaction Networks
2020cites this paper
Model checking randomized distributed algorithms
2020cites this paper
Verifying polymer reaction networks using bisimulation
2020influential citation
Message complexity of population protocols
2020influential citation
Time-space trade-offs in population protocols for the majority problem
2020cites this paper
Fault-tolerant simulation of population protocols
2020cites this paper
A stable majority population protocol using logarithmic time and states
2020cites this paper
Average-based Population Protocols : Explicit and Tight Bounds of the Convergence Time
2019cites this paper
Error-Free Stable Computation with Polymer-Supplemented Chemical Reaction Networks
2019cites this paper
Average-based Population Protocols : Explicit and Tight Bounds of the Convergence Time
2019cites this paper
Composable computation in discrete chemical reaction networks
2019cites this paper
Succinct Population Protocols for Presburger Arithmetic
2019influential citation
Sufficiency condition for output-oblivious chemical reaction networks and run-time analysis
2019cites this paper
Efficient Protocols for Peer-to-Peer Wireless Power Transfer and Energy-Aware Network Formation
2019cites this paper
On Design and Analysis of Chemical Reaction Network Algorithms
2018cites this paper
Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols
2018cites this paper
On Bioelectric Algorithms: A Novel Application of Theoretical Computer Science to Core Problems in Developmental Biology
2018cites this paper
Output-Oblivious Stochastic Chemical Reaction Networks
2018cites this paper
T he D istributed C omputing C olumn
2018cites this paper
Simple and Fast Approximate Counting and Leader Election in Populations
2018cites this paper
On the Computational Power of Simple Dynamics
2018cites this paper
1st Symposium on Simplicity in Algorithms, SOSA 2018, New Orleans, LA, USA, January 7-10, 2018
2018cites this paper
Exact size counting in uniform population protocols in nearly logarithmic time
2018cites this paper
Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols
2018influential citation
Simple and Efficient Leader Election
2018cites this paper
Fast Approximate Counting and Leader Election in Populations
2018cites this paper
Black Ninjas in the Dark: Formal Analysis of Population Protocols
2018cites this paper
Synthesizing and tuning stochastic chemical reaction networks with specified behaviours
2018cites this paper
Space-Optimal Proportion Consensus with Population Protocols
2017cites this paper
Advances in Parameterized Verification of Population Protocols
2017cites this paper
Friend or Foe? Population Protocols can perform Community Detection
2017cites this paper
Towards efficient verification of population protocols
2017influential citation
Computing models for networks of tiny objects
2017influential citation
Mediated Population Protocols: Leader Election and Applications
2017cites this paper
A Tool for Verification and Simulation of Population Protocols
2017cites this paper
Wireless charging for weighted energy balance in populations of mobile peers
2017cites this paper
Peer-to-Peer Wireless Energy Transfer in Populations of Very Weak Mobile Nodes
2017cites this paper
On the Power of Weaker Pairwise Interaction: Fault-Tolerant Simulation of Population Protocols
2016cites this paper
Stably Computing Order Statistics with Arithmetic Population Protocols
2016cites this paper
Nondeterministic seedless oritatami systems and hardness of testing their equivalence
2016influential citation
Programming with Chemical Reaction Networks: Mathematical Foundations
2016cites this paper
Interactive Wireless Charging for Weighted Energy Balance
2016cites this paper
Energy Balance with Peer-to-Peer Wireless Charging
2016cites this paper
Model Checking Population Protocols
2016cites this paper
Population Protocols with Faulty Interactions: The Impact of a Leader
2016cites this paper
Optimal proportion computation with population protocols
2016cites this paper
Verification of population protocols
2016influential citation
Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks
2016influential citation
Verifying Chemical Reaction Network Implementations: A Bisimulation Approach
2016cites this paper
Robustness of Expressivity in Chemical Reaction Networks
2016influential citation
Weak models of wireless distributed computing Comparison between radio networks and population protocols
2016cites this paper
Modular and Robust Computation with Deterministic Chemical Reaction Networks
2016cites this paper
Interactive Wireless Charging for Energy Balance
2016cites this paper
Stabilizing Consensus with Many Opinions
2015cites this paper
Synthesizing and Tuning Chemical Reaction Networks with Specified Behaviours
2015cites this paper
The Entropy of a Distributed Computing Schedule - the Example of Population Protocols
2015cites this paper
Information Spreading by Mobile Particles on a Line
2015cites this paper
Anonymous distributed computing: computability, randomization and checkability
2015cites this paper
The Computational Power of Beeps
2015cites this paper
Finite Automata with Multiset Memory: A New Characterization of Chomsky Hierarchy
2015cites this paper
Find Your Place: Simple Distributed Algorithms for Community Detection
2015cites this paper
Programming Chemical Kinetics: Engineering Dynamic Reaction Networks with DNA Strand Displacement
2015cites this paper
The Benefits of Entropy in Population Protocols
2015cites this paper
Polylogarithmic-Time Leader Election in Population Protocols
2015cites this paper
Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States
2015cites this paper
Swarms of Bouncing Robots
2014cites this paper
Minimal output unstable configurations in chemical reaction networks and deciders
2014influential citation
Speed faults in computation by chemical reaction networks
2014influential citation
Nothing can compare with a population, besides agents
2014cites this paper
Probability 1 computation with chemical reaction networks
2014cites this paper
Rate-independent computation in continuous chemical reaction networks
2014cites this paper
The computational capability of chemical reaction automata
2014cites this paper
Computability in Anonymous Networks: Revocable vs. Irrecovable Outputs
2014cites this paper