IO-PP[<] recognizes exactly the unambiguous star-free languages; stabilization is undecidable for PP[<] and IO-PP[+1] but conditionally decidable for IO-PP[<].
Fischer, and Ren \' e Peralta
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
verdicts
UNVERDICTED 5representative citing papers
Monadic Presburger predicates admit robust population protocols, with robustness incurring at least double-exponential state complexity cost and optimal constructions known for thresholds.
Structural liveness of conservative Petri nets is EXPSPACE-complete because minimal live markings are at most doubly exponential in net size.
All semilinear predicates and functions remain computable by CRNs under reverse-robust semantics using the same constructions, preserved by linear invariants.
Direct competition enables high-probability majority consensus in microbial populations for initial gaps Omega(sqrt(n log n)), while its absence requires Omega(n) gaps for constant probability.
citing papers explorer
-
Population Protocols over Ordered Agents
IO-PP[<] recognizes exactly the unambiguous star-free languages; stabilization is undecidable for PP[<] and IO-PP[+1] but conditionally decidable for IO-PP[<].
-
Monadic Presburger Predicates have Robust Population Protocols
Monadic Presburger predicates admit robust population protocols, with robustness incurring at least double-exponential state complexity cost and optimal constructions known for thresholds.
-
Structural Liveness of Conservative Petri Nets
Structural liveness of conservative Petri nets is EXPSPACE-complete because minimal live markings are at most doubly exponential in net size.
-
Reverse-Robust Computation with Chemical Reaction Networks
All semilinear predicates and functions remain computable by CRNs under reverse-robust semantics using the same constructions, preserved by linear invariants.
-
Reaching Agreement in Competitive Microbial Systems
Direct competition enables high-probability majority consensus in microbial populations for initial gaps Omega(sqrt(n log n)), while its absence requires Omega(n) gaps for constant probability.