ArticlesNo Access

ON THE LIMIT CYCLE STRUCTURE OF THRESHOLD BOOLEAN NETWORKS OVER COMPLETE GRAPHS

GEORGE VOUTSADAKIS

School of Mathematics and Computer Science, Lake Superior State University, 650 W. Easterday Avenue, Sault Sainte Marie, MI 49783, USA

This research was supported by a grant from the U.S. Department of Defense.

Search for more papers by this author

https://doi.org/10.1142/S0129065704001942Cited by:2 (Source: Crossref)

Abstract

In previous work, the limit structure of positive and negative finite threshold boolean networks without inputs (TBNs) over the complete digraph K_n was analyzed and an algorithm was presented for computing this structure in polynomial time. Those results are generalized in this paper to cover the case of arbitrary TBNs over K_n. Although the limit structure is now more complicated, containing, not only fixed-points and cycles of length 2, but possibly also cycles of arbitrary length, a simple algorithm is still available for its determination in polynomial time. Finally, the algorithm is generalized to cover the case of symmetric finite boolean networks over K_n.

Keywords:

AMSC: Primary 93A05, Primary 92B20, Secondary 68-04

References

F. J. Ballesteros and B. Luque, Physica A 313, 289 (2002), DOI: 10.1016/S0378-4371(02)01002-6. Crossref, Web of Science, Google Scholar
C. L. Barrett and C. M. Reidys, Applied Mathematics and Computation 98, 241 (1999), DOI: 10.1016/S0096-3003(97)10166-7. Crossref, Web of Science, Google Scholar
C. L. Barrett, H. S. Mortveit and C. M. Reidys, Applied Mathematics and Computation 107, 121 (1999), DOI: 10.1016/S0096-3003(98)10114-5. Crossref, Web of Science, Google Scholar
U. Bastolla and G. Parisi, Physica D 98, 1 (1996), DOI: 10.1016/0167-2789(96)00060-7. Crossref, Web of Science, Google Scholar
A. Bhattacharijya and S. Liang, Physical Review Letters 77, 1644 (1996). Crossref, Medline, Web of Science, Google Scholar
S. Bornholdt and K. Sneppen, Physical Review Letters 81, 236 (1998), DOI: 10.1103/PhysRevLett.81.236. Crossref, Web of Science, Google Scholar
B. Derrida and Y. Pomeau, Europhysics Letters 1, 45 (1986), DOI: 10.1209/0295-5075/1/2/001. Crossref, Google Scholar
B. Derrida and D. Stauffer, Europhysics Letters 2, 739 (1986), DOI: 10.1209/0295-5075/2/10/001. Crossref, Google Scholar
P. Döomöosi and C. L. Nehaniv, Mathematica Japonica 48, 481 (1998). Web of Science, Google Scholar
F. Fogelmann-Soulie , Y. Robert and M. Tchuente (eds.) , Automata Networks in Computer Science ( Princeton , 1987 ) . Google Scholar
F. Gécseg , Products of Automata , EATCS Monographs in Theoretical Computer Science 7 ( Springer Verlag , 1976 ) . Google Scholar
C. Gershenson, Classification of Random Boolean Networks, Artificial Life VIII: Proc. Eight Int. Conf. Anti Artificial Life, eds. R. Standishet al. (MIT Press, Massachussets, 2002) pp. 1–8. Google Scholar
C. Gershenson, J. Broekaert and D. Aerts, Contextual Random Boolean Networks, preprint . Google Scholar
E. Goles and S. Martíinez , Neural and automata networks dynamical behavior and applications , Mathematics and Its Applications ( Kluwer Academic Publishers , Dordrecht , 1990 ) . Crossref, Google Scholar
S. A. Kauffman, J. Theoretical Biology 22, 437 (1969), DOI: 10.1016/0022-5193(69)90015-0. Crossref, Medline, Web of Science, Google Scholar
S. A. Kauffman, Physica D 10, 145 (1984), DOI: 10.1016/0167-2789(84)90257-4. Crossref, Web of Science, Google Scholar
S. A. Kauffman, Physica D 42, 135 (1990), DOI: 10.1016/0167-2789(90)90071-V. Crossref, Web of Science, Google Scholar
S. A. Kauffman , The Origins of Order ( Oxford University Press , Oxford , 1993 ) . Crossref, Google Scholar
B. Luque and A. Ferrera, Complex Systems 11, 1 (1997). Web of Science, Google Scholar
B. Luque and R. V. Solé, Europhysics Letters 37, 597 (1997), DOI: 10.1209/epl/i1997-00196-9. Crossref, Google Scholar
B. Luque and R. V. Solé, J. Physics A: Mathematical and General 31, 1533 (1998), DOI: 10.1088/0305-4470/31/6/005. Crossref, Google Scholar
G. Voutsadakis, Applied Mathematics and Computation 142, 521 (2003), DOI: 10.1016/S0096-3003(02)00337-5. Crossref, Web of Science, Google Scholar
G. Voutsadakis, Combinatorial analysis of the state space structure of finite automata networks, preprint . Google Scholar