×

Combinatorics of sequential dynamical systems. (English) Zbl 1128.37006

Summary: We study sequential dynamical systems (SDS) over words. Our main result is the classification of SDS over words for a fixed graph \(Y\) and a family of local maps \((F_{v_i})\) by means of a novel notion of SDS equivalence. This equivalence arises from a natural group action on acyclic orientations. An SDS consists of: (a) a graph \(Y\), (b) a family of vertex indexed \(Y\)-local maps \(F_{v_i}:K^n\to K^n\), where \(K\) is a finite field and (c) a word \(w\), i.e. a family \((w_1,\dots,w_k)\), where \(w_j\) is a \(Y\)-vertex. A map \(F_{v_i}(x_{v_1},\dots, x_{v_n})\) is called \(Y\)-local iff it fixes all variables \(x_{v_j}\neq x_{v_i}\) and depends exclusively on the variables \(x_{v_j}\), for \(v_j\in B_1(v_i)\). The SDS-map is obtained by composing the local maps \(F_{v_i}\) according to the word \(w: [(F_{v_i})_{v_i\in Y},w]= \prod_{i=1}^k F_{w_i}:K^n\to K^n\). Mutual dependencies of the local maps arising from their sequential application are expressed in the graph \(G(w,Y)\) having the vertex set \(\{1,\dots,k\}\) (the indices of the word \(w\)) and in which \(r,s\) are adjacent iff \(w_s,w_r\) are adjacent in \(Y\). We prove a bijection from equivalence classes of SDS-words into equivalence classes of acyclic orientations of \(G(w,Y)\). We show that within these equivalence classes the induced SDS are equivalent in the sense that their respective phase spaces are isomorphic as digraphs.

MSC:

37B10 Symbolic dynamics
68R15 Combinatorics on words
05C20 Directed graphs (digraphs), tournaments
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI

References:

[1] Barrett, C.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E., On some special classes of sequential dynamical systems, Ann. Combin., 7, 4, 381-408 (2003) · Zbl 1060.68136
[2] Barrett, C.; Hunt, H. B.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E., Reachability problems for sequential dynamical systems with threshold functions, Theoret. Comput. Sci., 295, 1-3, 41-64 (2003) · Zbl 1045.68062
[3] P. Cartier, D. Foata, Problemes combinatoires de commutation et reárrangements, Lecture Notes in Mathematics, vol. 85, Springer, Berlin, 1969.; P. Cartier, D. Foata, Problemes combinatoires de commutation et reárrangements, Lecture Notes in Mathematics, vol. 85, Springer, Berlin, 1969. · Zbl 0186.30101
[4] Laubenbacher, R.; Pareigis, B., Equivalence relations on sequential dynamical systems, Adv. in Appl. Math., 26, 237-251 (2001) · Zbl 0986.37028
[5] Laubenbacher, R.; Pareigis, B., Decomposition and simulation of sequential dynamical systems, Adv. in Appl. Math., 30, 655-678 (2003) · Zbl 1027.37049
[6] Mortveit, H. M.; Reidys, C. M., Neutral evolution and mutation rates of sequential dynamical systems over words, Adv. Complex Systems, 7, 2-3, 395-418 (2005) · Zbl 1073.37019
[7] Mortveit, H. S.; Reidys, C. M., sequential dynamical systems, Discrete Math., 226, 281-295 (2000) · Zbl 1004.05056
[8] Reidys, C. M., Acyclic orientations of random graphs, Adv. in Appl. Math., 21, 181-192 (1998) · Zbl 0916.05062
[9] Reidys, C. M., On acyclic orientations and sequential dynamical systems, Adv. in Appl. Math., 27, 790-804 (2001) · Zbl 1017.68144
[10] Reidys, C. M., Certain morphisms of sequential dynamical systems, Discrete Math., 296, 2-3, 245-257 (2005) · Zbl 1079.37007
[11] Reidys, C. M., Sequential dynamical systems over words, Ann. Combin., 10, 481-498 (2006) · Zbl 1130.37334
[12] Schreckenberg, M.; Schadschneider, A.; Nagel, K.; Ito, N., Discrete stochastic models for traffic flow, Phys. Rev. E., 51, 4, 2939-2949 (1995)
[13] Wei, G. H.; Liu, D. P.; Liang, C. C., Charting gene regulatory networks: strategies, challenges and perspectives, Biochem. J., 381, 1 (2004)
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.