Program
12/4/2023
9:00-9:45 Registration and welcome
9:45-10:00 Welcome
Discrete systems
10:00:10:30 Danuta Makowiec
Synchronization in a network of controlled oscillatory cellular automata
10:30-11:00 Barbara Wolnik, M. Dziemianczuk
Differences between the case of finite grids and the case of the infinite grid in the context of number conservation of non-uniform cellular automata
We focus on non-uniform Elementary Cellular Automata (ECAs), i.e. one-dimensional cellular automata whose cells can use different Wolfram’s rules to update their states. In the paper B. Wolnik, M. Dziemianczuk, B. De Baets, Non-uniform number-conserving
elementary cellular automata (Information Sciences 626 (2023) 851–866.
doi:10.1016/j.ins.2023.01.033) a detailed characterization of number-conserving such CAs has been presented in the case of finite grids both with periodic and null boundary conditions. It appears that the case of the infinite grid is a little more complicated and it contains types of number-conserving non-uniform ECAs that do not occur in the case of finite grids.
11:00-11:30 coffee break
11:30-12:00 Maciej Wołoszyn
Structural balance and social noise: from triangular networks to random graphs
Dynamics of social relations may be described in terms of the so-called structural balance (or Heider balance), based on the concept of triads of actors. In each of those triads, it is easy to decide if the arrangement of relations (friendly or hostile) is balanced or not, following the simple rules: 'a friend of my friend is my friend,' 'a friend of my enemy is my enemy,' etc. In addition to the natural tendency of social systems to tend to equilibrium, we also add the random factor of social noise, or social temperature, which also affects the dynamics of the system and may prevent or allow reaching a balanced state. All of this is strongly dependent on the structure of the network of relations between the actors. The presented results concentrate on networks that include regular triangular lattices, networks created by random modification of such lattices by adding or removing some of the connections, and networks modelled with classical random graphs of various densities. Our simulations show how the parameters of the network and the value of the noise level influence the possibility of reaching a balanced state.
[1] Maciej Wołoszyn, Krzysztof Malarz, Phys. Rev. E 105, 024301 (2022)
[2] Krzysztof Malarz, Maciej Wołoszyn, Chaos 30, 121103 (2020)
[3] Krzysztof Malarz, Maciej Wołoszyn, Krzysztof Kułakowski, Physica D 411, 132556 (2020)
[4] Krzysztof Malarz, Maciej Wołoszyn, arXiv:2206.14226
12:00-12:30 Michiel Rollier
Non-uniform cellular automata
Non-uniform cellular automata (nuCAs) are an extension to elementary CAs, for which different cells are allowed to follow different transition rules. These are primarily investigated to increase knowledge on heterogeneous dynamical systems.
The additional complexity of non-uniformity allows for much richer behaviour than in the elementary case, because of two main reasons. First, even when only allowing two transition rules, the rule space increases in size from 256 to 256^2. Second, the allocation of the rules (""which cells follow which rules"") vastly increases the number of initial conditions.
One approach to investigating nuCAs is to perform many simulations, to examine the resulting spacetime diagrams, and to classify its behaviour. After all, we would be very interested in combinations of rules or particular types of initial rule allocations that bring about unexpected behaviour. Classification for elementary CAs typically occurs into one of six Li-Packard classes. Considering said complexity in outcome, classification by hand for nuCAs would be a highly tedious task.
Because spacetime diagrams are essentially texture images, convolutional neural networks (CNNs) that are specialised for texture recognition can be used to classify nuCA behaviour. In this work, we present a simple approach, first using CNNs to classify elementary CAs into one of six Li-Packard classes. Next, demonstrating how the trained algorithm succeeds and fails when applied to nuCAs.
We finish our talk by presenting a number of possible ways forward, including the addition of out-of distribution detection.
12:30-13:00 Raffaele Marino
Hard Optimization Problems have Soft Edges
Finding a Maximum Clique is a classic property test from graph theory; find any one of the largest complete subgraphs in an Erdös-Rényi 𝐺(𝑁,𝑝) random graph. It is the simplest of many such problems in which algorithms requiring only a small power of 𝑁 steps cannot reach solutions which probabilistic arguments show must exist, exposing an inherently ""hard"" phase within the solution space of the problem. Such ""hard"" phases are seen in many NP-Complete problems, in the limit when 𝑁 → ∞. But optimization problems arise and must be solved at finite N. We use this simplest case, MaxClique, to explore the structure of the problem as a function of 𝑁 and 𝐾, the clique size. It displays a complex phase boundary, a staircase of steps at each of which 2log_2 𝑁 and 𝐾_{max}, the maximum size of clique that can be found, increase by 1. Each of its boundaries have finite width, and these widths allow local algorithms to find cliques beyond the limits defined by the study of infinite systems. We explore the performance of a number of extensions of traditional fast local algorithms, and find that much of the ""hard"" space remains accessible at finite 𝑁.
The ""hidden clique"" problem embeds a clique somewhat larger than those which occur naturally in a 𝐺(𝑁,𝑝) random graph. Since such a clique is unique, we find that local searches which stop early, once evidence for the hidden clique is found, may outperform the best message passing or spectral algorithms.
13-14:30 Lunch and discussion
14:30-15:00 Rolf Hoffmann
Patterns defined by Tiles and generated by 1D Cellular Automata
Patterns can be be generated by Cellular Automata using overlapping tiles [1, 2]. This method is applied and investigated in detail for 1D pattern with cell states in {0, 1, 2}. Templates (local matching patterns) are derived from a given set of tiles. A tile consists of pixels taken from the set {0, 1, 2, *}, where '*' represents a Don't Care. A pattern is 'valid' if the whole space is covered by the given tiles that may overlap. The overlap (cover level) can be approximated by template hits. Depending on the cover level at each site, noise is injected that drives the evolution to a valid pattern. Depending on the amount of noise and the cover level, the density of the used tiles can be controlled in the range between the maximum and minimum. The influence of different updating schemes (synchronous, asynchronous, sequential) and initial conditions is also discussed.
[1] Hoffmann, R.:Forming Point Patterns by a Probabilistic Cellular Automata Rule. Presented at Summer Solstice Conference on Complex Systems (2019); eprint arXiv:2202.06656 (2022)
[2] Hoffmann R., Désérable D., Seredyński F.: A Probabilistic Cellular Automata Rule Forming Domino Patterns. In: Malyshkin V. (eds) Parallel Computing Technologies (2019). LNCS vol 11657, pp. 334-344, Springer
15:00-15:30 Milan Vispoel
The structure of the cellular automata rule space
The rule space that corresponds to a certain family of cellular automata (CA) has no inherent structure to it. There have been various attempts to impose a structure on such rule spaces. Usually, the rule space is parameterized by defining a way to extract a parameter based on the CA's rule table. In this paper, we define a new approach to parameterize the rule space based on mean-field theory. This allows us to draw analogues between a CA's rule table and the update equation of a discrete dynamical system. So far, parameterizations of the rule space have been investigated solely in a qualitative way. Here we will instead investigate such parameterizations in a quantitative way by considering the supervised multiclass classification problem of predicting a CA's Wolfram class based on the rule table parameters. In this way, we are able to quantitatively analyze and compare various ways to impose a structure on a CA rule space. In addition to revealing the dynamical and information theoretical-based structure of a CA rule space, our approach also provides a useful way to predict the behavior of a CA based on its rule table, which is an undecidable problem.
15:30-16:00 Henryk Fukś [online]
Algorithmic beauty of finite state machines
One of the most interesting problems in the theory of complex systems is the forward problem: given the state of the system now, what can we say about its future state? Cellular automata are often considered to a paradigm of complex systems, and the forward problem for some selected classes of them can be ``solved'' in both deterministic and probabilistic sense. On of the most fruitful method for doing this is to use properties of preimages of finite blocks. Finite state machines can be used to describe preimage sets, and some of them reveal striking symmetries and regularities. We will present examples of such finite state machines, both ""beautiful"" and ""ugly"", and demonstrate how they are used in solving the forward problem for CA.
16:00-16:30 Coffee break
16:30-17:00 Miroslaw Szaban
The Airborne Contaminant Source Reconstruction With Use of the Cellular Automaton and Sandpile Model.
The paper presents an approach of the Sandpile Model to prediction the source of the airborne contaminant in the low urbanized area.The aim of this study is to propose an approach for contamination source localization with use of model using the Generalized Extremal Optimization (GEO) algorithm with the Sandpile model. Sandpile model was used to calculating the value of the evaluation function, which will be able to effectively simulate the transport of atmospheric contamination in open areas. The GEO algorithm searched for the contamination source localization comparing the results form Sandpile model and the data reported by the sensors monitoring the considered area (e.g., contaminant concentration).
17:00-17:30 Anna Nenca
The parity problem for cellular automata
The parity problem, in its classical formulation, is to find a CA that can properly classify each initial configuration into two classes according to its parity: if the initial configuration contains an odd number of 1s then the global state of the grid should converge to the fixed point of all 1s; otherwise, i.e., if the initial configuration contains an even number of 1s then the global state of the grid should converge to the fixed point of all 0s. This problem appears to be much harder than the DCP because the output is altered simply by a flip in any one of the input bits. Moreover, according to the formulation of the problem, it is immediately obvious that it has no sense for even-sized grids (see, for example, [1]). For this reason, the solution to this problem is considered to be a CA (actually: a local rule f), which correctly classifies all configurations of odd length.
It turns out that the parity problem has a solution. In [1] Betel et al. described the local rule with radius 4 (i.e., the size of the neighborhood is equal to 9), called BFO rule, that solves the parity problem. The BFO rule was constructed by analyzing the properties of the De Bruijn graph of the rule, that preserves parity and converges correctly for any initial configuration to a homogeneous configuration. In the same paper it was shown that there is no binary CA with radius at most two (i.e., for neighborhood size not greater than 5) that would solve the parity problem for all odd-sized grids.
They also leave open the question of whether there is a rule of radius 3 (i.e., with a neighborhood size of 7) that solves the parity problem. They attempted to find the perfect rule using a sophisticated evolutionary algorithm. After many trials, they made the following conjecture: Conjecture 1 The perfect solution to the parity problem with the neighborhood of size 7 does not exist.
Although the results presented in [1] are magnificent, the authors have left a fairly wide gap, because the paper does not contain any results for neighborhoods of size 6, 7, or 8. Today, 10 years after publication, the results have still not been improved and the gap has not been narrowed.
[1] H. Betel, P. P. Oliveira, and P. Flocchini. Solving the parity problem in one-dimensional cellular
automata. Natural Computing: An International Journal, 12(3):323–337, 2013.