Presburger Arithmetic

[Erik Winfree]

Presburger arithmetic comes up naturally in the theory of stochastic discrete chemical reaction networks, specifically, in questions of reachability.  E.g., with some given set of reactions, starting with exactly 17X and 8 Y, is there a series of reactions that might occur to bring the state to being exactly 1 P and 2 Q ?  This problem is (but for notation) identical to or equivalent to reachability questions in Petri Nets and Vector Addition Systems, but for me, the connection to fundament chemistry makes it more “natural”.  The connection to Presburger arithmetic can be found in the extensive and brilliant works of Jérôme Leroux, for example (but also see his more recent work):

"Vector Addition Systems Reachability Problem (A Simpler Solution)”
J Leroux - EPiC, 2012
https://hal.archives-ouvertes.fr/hal-00674970/ <https://hal.archives-ouvertes.fr/hal-00674970/>.  

For some out-of-date background, forgive me for self-citing:
"Programmability of chemical reaction networks"
M Cook, D Soloveichik, E Winfree, J Bruck - Algorithmic bioprocesses, 2009 
https://link.springer.com/chapter/10.1007/978-3-540-88869-7_27 <https://link.springer.com/chapter/10.1007/978-3-540-88869-7_27>

And for a more up-to-date view of the connection to chemistry:
Computing with chemical reaction networks: a tutorial
R Brijder - Natural Computing, 2019 
https://link.springer.com/article/10.1007/s11047-018-9723-9 <https://link.springer.com/article/10.1007/s11047-018-9723-9>

Of course, I imagine that you may be thinking of “natural” in terms of mathematical naturalness…. and even here I think that the Vector Addition System formulation might serve your purpose.

Erik

> On Jul 18, 2022, at 11:19 PM, JOSEPH SHIPMAN <joeshipman at aol.com> wrote:
> 
> Does anyone know a natural decidable problem that is equivalent to Presburger Arithmetic? (Presburger Arithmetic has a complexity lower bound of nondeterministic double exponential time and an upper bound of double exponential space).
> 
> — JS
> 
> Sent from my iPhone

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220719/a78e13fb/attachment-0001.html>