Schedule

WAN will take place entirely at the ESPRIT building.

Kevin Perrot
Rice-like complexity lower bounds for automata networks
I will survey recent advances on general complexity lower bounds for automata networks, basically establishing that, for any MSO sentence φ, the problem of deciding whether the dynamics of a given automata network verifies phi is either O(1), or NP-hard, or coNP-hard. MSO sentences offer a general framework to define graph-theoretic properties, such as the existence of fixed points, bijectivity, connectedness, etc. Precisely, the statements have subtleties and variants, that we now better understand using modern tools from finite model theory applied to so called cliquewidth.
 

Maximilien Gadouleau
Boolean networks and their trapspaces
A trapspace is an invariant subcube of a Boolean network (BN). In this talk, we shall first investigate what happens when two BNs have the same collections of trapspaces. This will lead us to define "trapping" BNs; we shall explore their structure and show that they are closely related to commutative BNs.
 

Bastien Chopard
Characterization of collective behaviors of autonomous vehicles using a discrete numerical model
The impact on traffic fluidity of a collection of autonomous cars is discussed in this presentation.  Autonomous vehicles offer the possibility to control their behaviors by algorithms out of reach of human drivers. Here we consider the problem of lanes merging, a situation that often causes severe traffic jams on highways. We propose an algorithm that allows autonomous cars to switch from a two-lane flow to a one-lane flow, without having to reduce speed. Collectively, this algorithm has consequences on the traffic at large scale. We show how the various parameters of the algorithm affect the global traffic pattern and the efficiency of the process.
 

Noa Izsak
Learning Broadcast Protocols
The problem of learning a computational model from examples has been receiving growing attention. For the particularly challenging problem of learning models of distributed systems, existing results are restricted to models with a fixed number of interacting processes. In this work, we look for the first time at the problem of learning a distributed system with an arbitrary number of processes, assuming only that there exists a cutoff, i.e., a number of processes that is sufficient to produce all observable behaviors. Specifically, we consider fine broadcast protocols, these are broadcast protocols (BPs) with a finite cutoff and no hidden states. We provide a learning algorithm that can infer a correct BP from a sample that is consistent with a fine BP, and a minimal equivalent BP if the sample is sufficiently complete. On the negative side we show that (a) characteristic sets of exponential size are unavoidable, (b) the consistency problem for fine BPs is NP-Hard, and (c) that fine BPs are not polynomially predictable.
 

Anna Nenca, Barbara Wolnik
One-side parity problem for cellular automata
The parity problem is a classic benchmark for the testing of the computational power of cellular automata. In the traditional formulation, the problem involves cyclic configurations of odd length, which should converge to a fixed point of all 0s or all 1s based on the initial number of 1s, without global access to the sequence. We are interested in exploring a kind of “halfway solutions", i.e., CAs that correctly classify all even configurations or all odd configurations. In particular, we are interested in whether there is a local rule solving the one-side parity problem that is less complicated (i.e. has a smaller neighborhood size) than the local rules solving the classical problem.
 

Florian Bridoux
Interaction Graph of Hamiltonian Automata Networks
An automata network with n components over a finite alphabet A is a discrete dynamical system described by the successive iterations of a function f: Aⁿ → Aⁿ. In other words, if at step t, the configuration of the system is x = (x₁, ..., x_n), then at step t+1, the configuration is f(x) = (f₁(x), ..., f_n(x)). The interaction graph of f is the directed graph with vertex set {1, ..., n} and an arc from vertex j to vertex i if f_i(x) depends on the input x_j for some x. In this talk, we aim to characterize the interaction graphs of Hamiltonian automata networks: automata networks whose dynamics form a unique cycle of length |A|ⁿ.