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.7538348436355591
0 references
0.7486359477043152
0 references
0.7418015599250793
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