×

Combinatorics of life and death for reaction systems. (English) Zbl 1192.68458

Summary: Reaction systems are a functional model of interactions between biochemical reactions. They define functions on finite sets (over a common finite domain). In this paper, we investigate combinatorial properties of functions defined by reaction systems. In particular, we provide analytical approximations of combinatorial properties of random reaction systems, with a focus on the probability of whether a system lives or dies. Based on these results, we can create parameterized random reaction systems that rarely die. We also empirically analyze the length of time before such a system enters cyclic behavior, and find that the time is related to the behavior of completely random functions on a smaller domain.

MSC:

68R05 Combinatorics in computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldous D., Applied Mathematical Sciences #77, in: Probability Approximations via the Poisson Clumping Heuristic (1988)
[2] Ehrenfeucht A., Fundamenta Informaticae 76 pp 1–
[3] DOI: 10.1016/j.tcs.2007.01.008 · Zbl 1119.93011 · doi:10.1016/j.tcs.2007.01.008
[4] DOI: 10.1016/j.tcs.2008.09.043 · Zbl 1156.93306 · doi:10.1016/j.tcs.2008.09.043
[5] DOI: 10.1016/0377-0427(93)E0258-N · Zbl 0826.33001 · doi:10.1016/0377-0427(93)E0258-N
[6] DOI: 10.1007/BF01325639 · doi:10.1007/BF01325639
[7] DOI: 10.1214/aoms/1177705677 · Zbl 0158.34905 · doi:10.1214/aoms/1177705677
[8] Knuth D. E., The Art of Computer Programming (Volume 1), Fundamental Algorithms (1968) · Zbl 0191.17903
[9] Knuth D. E., The Art of Computer Programming (Volume 2), Seminumerical Algorithms (1969) · Zbl 0191.18001
[10] O’Cinneide C. A., Annals of Applied Probability 10 pp 1151–
[11] Ramanujan S., J. Indian Math. Soc. 3 pp 128–
[12] Ramanujan S., J. Indian Math. Soc. 4 pp 151–
[13] Watson G. N., Proc. London Math. Soc. 29 pp 293–
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.