No label defined (Q3823809)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4098733
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4098733

      Statements

      1988
      0 references
      cellular automata
      0 references
      asymptotic behavior
      0 references
      energy function
      0 references
      minimum function
      0 references
      0 references
      0 references
      The following system is considered: Let G be an undirected graph and \(x_ i(0)\) be a function assigning an integer to each node i of G. This function is synchronously updated at every step according to the scheme \((J_ i\) denotes the set of nodes adjacent to i) \[ x_ i(t+1) = \begin{cases} x_ i(t)-1 &\text{ if }\sum_{j\in J_ i}x_ j(t) - | J_ i| x_ i(t) < 0; \\ x_ i(t) &\text{ if \(x_ j(t) = x_ i(t)\) for all \(j\in J_ i;\) } \\ x_ i(t)+1, &\text{ otherwise.} \end{cases} \] Repeating this procedure the function x runs into a cycle of length one or two. The present paper introduces an upper bound for the number of steps to be provided until the cycle is reached. The method to prove this result is based on a new ``energy function'' containing in addition to linear and bilinear terms the minimum function.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references