Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

15 mars 2021


Sylvain Sené (LIS, Aix Marseille University)


8 mars 2021

Computability, universality and quantum automata

Pablo Arrighi (LRI - University of Paris-Saclay )

I will draw a distinction between finite-dimensional quantum evolutions (“automata“) and infinite-dimensional evolutions (“operators”), and then explore their consequences upon two well-established concepts in Computer Science : computability and universality. Most of the results I will mention will rely on a decomposition of quantum operators, into quantum cellular automata—which is based upon the tacit assumption of a fixed partial order. Time-allowing, I will try to touch on the topical question of quantum partial orders.

22 février 2021


Nathan Grosshans (Theoretische Informatik / Komplexe Systeme, Universität Kassel)

15 février 2021

A type theoretic appraoch to weak omega-categories


Weak omega-categories are a very challenging concept to study rigorously in mathematics, as the axioms defining them are very intricate and complicated to verify. In this talk I will present a way of dealing with this complexity algorithmically, by designing a language relying on dependent type theory. This language allows for the implementation of an interactive theorem prover “CaTT” dedicated to work with weak omega-category. I will then present the semantics of this language and formally relate its models with anterior notions of weak omega-categories, which is the main contribution of my PhD thesis.

8 février 2021


Guillaume Dupont (INP Toulouse)


1 février 2021

Rice-like theorems for automata networks

Guilhem Gamard (aboratoire d’Informatique et Systèmes, Aix-Marseille)

An automata network (AN for short) is a finite digraph where each node holds a state, chosen among a finite set,
that evolves in function of the states of its inbound neighbors.
Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in an cellular automaton.
In other terms, the differences between a cellular automaton and an automata network is that the
“grid” is an arbitrary finite digraph, and that different nodes may have different update functions.
ANs have been used to model neural networks, dynamics of expression and inhibition of genes,
distributed algorithms, and more.

Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory.
Still, they are subject to some kind of “Rice theorems”, i.e., results along the lines of:
“any nontrivial property of the function computed by an automata network is computationally hard to test”.
In this talk, we will review several results that fit this pattern,
as well as pieces of proof that hopefully may be reused in other contexts.

25 janvier 2021

Exploring many solutions of many CA problems: The Formal Notion of Local CA Simulation

Tien Thao Nguyen (LACL)

We revisit the notion of local simulation of a Cellular Automaton (CA), which allows to transform a cellular automaton into a closely related one with different local encoding of information.

This notion is useful to explore the solution space of many CA problems, in particular we investigate two well studied one dimensional CA problems, namely the Firing Squad Synchronization Problem and the Sequence Generator problem.

1. For the Firing Squad Synchronization Problem we exhibit many solutions that are minimal both in time (2n-2 for n cells) and, up to current knowledge, also in states (6 states). This improves from the solution proposed by Mazoyer in 1987; and more recently the 718 new solutions generated by Clergue, Verel and Formenti in 2018 with a cluster of machines.
Using local simulations, we show how to generate millions of such 6-state solutions.

2. The Sequence Generator problem on the CA model has been studied since at least 1960 and numerous generation algorithms have been proposed for a variety of non-regular sequences such as {2^n | n = 1, 2, 3, …}, the primes, Fibonacci sequences etc.
Using the 6-state solution of Kamikawa and Umeo of read-time sequence generator for the cubes {n^3 | n = 1, 2, 3, …}, we handcrafted a 5-state reduction for this solution and then showed how to generate several million of solutions from this 5-state solution.
It is notable that in contrast to the current ubiquity of cloud computing, we used only a modest personal computer thanks to the nice algorithmic properties of local simulations.

18 janvier 2021

The Bicategory of “Open Functors” and its Friends

Luidnel Maignan (LACL)

On one hand, one often contrasts open dynamical systems with “ordinary/closed” dynamical systems, while knowing that, formally, open dynamical systems are a particular case of dynamical systems in many instances. On the other hand, a closed dynamical system is essentially a (collection of) function from a set X to itself. How to formalize “open” functions from a set X to another set Y ? This building block is necessary when designing a system as a composition of many modules. Also, how to formalize “open” functors from a category C to another category D. This building block is necessary when the dynamical system has some notion of “locality” and “space”. These questions arose in the study of so-called Global Transformations, dynamical systems where the space might be arbitrary and evolving concurrently and synchronously. In this talk, we begin by formalizing the matter as directly as possible with respect to the intuition. Then we connect the obtained construction to existing frameworks via three points of view. This might be seen as a (pedagogical ?) entry point to many categorical ideas starting from the simple ground of cellular automata. This is based on works in progress with Alexandre Fernandez and Antoine Spicher.