×

zbMATH — the first resource for mathematics

On pre-periods of discrete influence systems. (English) Zbl 0611.93046
We investigate sequences \(\{y_ k\}^{\infty}_{k=0}\) of vectors defined by \(y_{k+1}=f(Ay_ k)\) where A is a symmetric matrix and f is a gradient (or subgradient) of a convex function. Special transformations of this type are often considered in connection with cellular automata. We proved earlier [Discrete Appl. Math. 13, 27-32 (1986; Zbl 0588.93048)] that the only possible periods of such a sequence are 1 or 2. Here we give upper bounds on the number of steps before a period in cases \(f(x)=(f_ 1(x_ 1),...,f_ n(x_ n))\) where the \(f_ i's\) are threshold, multi-threshold or, if the \(x_ i's\) are vectors of lower dimension, cyclically monotone functions. The bound is tight for threshold functions.

MSC:
93C55 Discrete-time control/observation systems
26B25 Convexity of real functions of several variables, generalizations
68Q80 Cellular automata (computational aspects)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
33E99 Other special functions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Caianello, E.R.; De Luca; Ricciardi, L., Reverbations and control of neutral networks, Kybernetik, 4, (1967)
[2] French, J.R.P., A formal theory of social power, Psych. review, 63, 181-194, (1956)
[3] Goles, E.; Olivos, J., Comportement itératif des fonctions à multiseuil, Information and control, 45, 300-313, (1980) · Zbl 0445.94047
[4] Goles, E.; Olivos, J., Comportement périodique des fonctions à seuil binaries et applications, Discrete appl. math., 3, (1981) · Zbl 0454.68042
[5] J. Pelant, S. Poljak and D. Turzik, Cyclically monotonous evaluation in social influence models, submitted to Math. Oper. Res.
[6] Poljak, S.; Sůra, M., On periodical behaviour in societies with symmetric influences, Combinatorica, 3, 119-121, (1983) · Zbl 0561.90008
[7] Poljak, S.; Turzik, D., On systems, periods, and semipositive mappings, Comm. math. univ. carolinae, 25, 4, 597-614, (1984) · Zbl 0576.05059
[8] Poljak, S.; Turzik, D., On an application of convexity to discrete systems, Discrete appl. math., 13, 27-32, (1986) · Zbl 0588.93048
[9] Roberts, F.S., Discrete mathematical models, with application to social, biological, and environmental problems, (1976), Prentice-Hall Englewood Cliffs, NJ
[10] Rockafellar, R.T., Convex analysis, (1970), Princeton Univ. Press Princeton, NJ · Zbl 0229.90020
[11] Fogelman, F.; Goles, E.; Weisbuch, G., Transient length in sequential iterations of threshold functions, Discrete appl. math., 6, 95-98, (1983) · Zbl 0506.39004
[12] Goles, E.; Fogelman, F.; Pellegrin, D., Decreasing energy functions as a tool for studying threshold networks, Discrete appl. math., 12, 261-277, (1985) · Zbl 0585.94018
[13] E. Goles, Dynamics on positive automata networks, Theor. Comput. Sci., to appear. · Zbl 0585.68059
[14] Harary, F., A criterion for unanimity in French’s theory of social power, (), 168-182
[15] Poljak, S.; Turzik, D., Social influence models with ranking alternatives and local election rules, Math. soc. sci., 10, 189-198, (1985) · Zbl 0586.90005
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.