10-13 juil. 2017 Paris (France)

Résumés

 
Nathalie Aubrun
 
An application of Lovász local lemma in Symbolic Dynamics
 
 

Symbolic Dynamics is the study of subshifts, that are sets of colorings of Z^d (or another finitely generated group) by a finite alphabet, that respect some local constraints. To prove that a subshift is non empty, it is enough to exhibit a coloring that satisfies the constraints. In this talk, I will explain how Lovász local lemma can be helpful to prove non-emptiness of subshifts. As an application, we will show the existence of a strongly aperiodis subshift on any finitely generated group.
This is joint work with Sebastián Barbieri and Stéphan Thomassé.

 

Laurent Bartholdi
 
Amenability
 
Amenability is one of the fundamental properties of infinite groups. In all cases, one learns something valuable about the group: if it is amenable, then its actions on various geometric objects must have fixed points; if it is non-amenable, then it admits paradoxical decompositions: finite partitions whose pieces, after left-translation, can be rearranged in two copies of the original group.
 
Remarkably, groups generated by automata served as a prominent source of examples of amenable groups, delineating quite richly the boundary between amenable and non-amenable. I will outline some constructions of groups generated by automata and some fundamental open questions.
 
 
 
Tara Brough
 
The power of symbol-tuples for automaton semigroup constructions
 
In 2014, Cain and I made the following conjectures [1], giving a proposed `small' counterexample in each case:
 
Conjecture 1  The class of automaton semigroups is not closed under taking free products.
 
Conjecture 2  The class of automaton monoids is not closed under taking wreath products with finite top monoid.
 
Both of our proposed counterexamples are in fact automaton semigroups, and Conjecture 2 is false [2].  What we were missing was that it turns out to be very powerful, in attempting to construct new automaton semigroups from known examples, to use tuples of symbols from the 'base' automata as the symbols of the new automaton.
 
In this talk I will illustrate several ways of using symbol-tuples to realise various standard semigroup constructions -- such as free products, wreath products, strong semilattices and Rees matrix constructions (under certain conditions) -- as automaton semigroups.
 
[1]  T. Brough and A.J. Cain, `Automaton semigroup constructions', Semigroup Forum 90(3), 763--774 (2014).
[2]  T. Brough and A.J. Cain, `Automaton semigroups: new constructions results and examples of non-automaton semigroups', Theoret. Comput. Sci. 674, 1--15 (2017).
 
 

Alan J. Cain 

Automaton, automatic, FA-presentable: comparing three automata-theoretic approaches to semigroups

An automaton semigroup is defined as the semigroup generated by the action of a Mealy automaton. An automatic structure for a semigroup (a concept which emerged in the late 1990s as a generalization of automatic structures for groups as studied by Epstein et al.) describes a semigroup in terms of a regular language of normal forms and synchronous rational relations that describe right-multiplication of elements by generators in terms of those normal forms. An FA-presentation (also called an automatic presentations, a concept developed by Khoussainov & Nerode as a means of extending finite model theory to infinite structures while maintaining decidability of interesting problems) describes a relational structure in terms of a regular language of abstract representatives for its elements (not necessarily words over a generating set) and synchronous rational relations describing each of its relations in terms of those representatives (viewing $n$-ary operations as $(n+1)$-ary relations).

This talk will be a survey, comparing and contrasting these three ways of describing and computing with semigroups. The main foci will be the kinds of examples that arise in these classes, their behaviour under semigroup constructions, decision problems, and connections between these classes.

 

Daniele D'Angeli

Automaton (semi)groups: on the undecidability of some problems

In this talk I present some results obtained in collaboration with T. Godin I. Klimann, M. Picantin, E. Rodaro, and J-P. Wächter.
We consider algorithmic problems for automaton semigroups and automaton groups of the freeness and finiteness kind. We first show that checking whether an automaton group has empty set of positive relations is undecidable. Moreover we prove that the emptyness of the set of positive relations is equivalent to the dynamical property of having all the orbital graphs centred at the non-singular points which are acyclic. We also settle the problem of checking the freeness for the semigroup defined by an automaton group by proving that such problem is undecidable. We also obtain that the finiteness problem for automaton subsemigroups of inverse automaton semigroups is also undecidable. Finally, motivated by the finiteness problem, we consider the problem whether the infiniteness of automaton semigroup is equivalent to the existence of an infinite orbital graph. We conjecture that for automaton groups this is the case. As a partial support to this conjecture, we show that for reversible automaton groups this holds true.

 

Martin Delacourt

Permutive one-way cellular automata and the finiteness problem for automaton groups

The decidability of the finiteness problem for automaton groups is a well-studied open question on Mealy automata. We connect this question of algebraic nature to the periodicity problem of one-way cellular automata, a dynamical question known to be undecidable in the general case. We provide a first undecidability result on the dynamics of one-way permutive cellular automata, arguing in favor of the undecidability of the finiteness problem.

 

Francesca Fiorenzi

Entropy of strongly irreducible subshifts

Let A be a finite alphabet. If X is an irreducible sofic subshift of A^Z and Y is a proper subshift of X, it is well known that ent(Y) < ent(X). The proof of this result is generally based on the Perron-Frobenius theory.

We present a purely combinatorial proof of this theorem and we discuss some possible generalizations to a strongly irreducible subshift of A^G, where G is an amenable group.

This is a joint work with Filippo Mignosi.

 

Pierre Gillibert

Simulating Turing machines with invertible Mealy automata

From any Turing Machine, with a one-direction infinite tape, we construct an invertible Mealy Automaton. The corresponding automaton group simulates the Turing Machine in the following sens: given any entry word there is an (explicitly constructed) element of the group such that the Turing Machine stops on this entry if and only if the order of the element is finite.

In particular, considering  an automaton group constructed from a universal Turing Machine, there is no algorithm which decides whether or not an element is of finite order.

 

Markus Lohrey

Knapsack and subset sum for groups beyond the integers

(joint work with Daniel König and Georg Zetzsche)

Recently, Myasnikov, Nikolaev and Ushakov considered classical knapsack related decision problems for arbitrary finitely generated (f.g.) groups instead of the group of integers (the classical case).
Among others, they studied the following problems for a f.g. group G (where elements of G are represented by finite words over the generators):

  • Subset sum problem for G:

Given elements g_1,..., g_k, g of G, decide whether there exist numbers e_1,..., e_k from {0,1} such that g = g_1^{e_1} … g_k^{e_k}.

  • Knapsack problem for G:

Given elements g_1,...,g_k, g of G, decide whether there exist natural numbers e_1,..., e_k such that g = g_1^{e_1} … g_k^{e_k}.

In the talk, I will speak about some recent results for knapsack and subset sum in various classes of groups: nilpotent groups, polycyclic groups, right-angled Artin groups (aka graph groups), co-context free groups, certain wreath products. More precisely, we will discuss the following results and (if time permits) will prove some of them:
- There exists a f.g. 2-step nilpotent group G with an undecidable knapsack problem.
- For every co-context-free group, knapsack is decidable.
- Knapsack in right-angled Artin groups is in NP, and one can exactly characterize those graph groups where knapsack is NP-complete.
- Knapsack is decidable for a large class of wreath products.

  

Jean Mairesse

Uniform measures on braid monoids

We are interested in the asymptotic properties of typical positive braids, respectively positive dual braids. Denoting by μk the uniform distribution on positive (dual) braids of length k , we prove that the sequence (μk)k converges to a unique probability measure μ on infinite positive (dual) braids. The key point is that the limiting measure μ has a Markovian structure which can be described explicitly using the combinatorial properties of braids encapsulated in the Möbius polynomial. As a by-product, we settle a conjecture by Gebhardt and Tawn (J. Algebra, 2014) on the shape of the Garside normal form of large uniform braids.

Joint work with S. Abbes, S. Gouëzel and Vincent Jugé

 

Irène Marcovici

Ergodicity of Noisy Cellular Automata: The Coupling Method and Beyond

When perturbating a cellular automaton by a random noise (positive probability of error, for each cell independently), the system is generally expected to be ergodic, meaning that during its evolution, it eventually forgets about its initial condition. For a high noise, this can be shown by coupling. However, for a small noise, ergodicity is often very difficult to prove. We present extensions of the coupling method to small noises when the cellular automaton has some specific properties (hardcore exclusion, nilpotency, permutivity).

 

Cyril Nicaud

Random automata

We’ll survey various result on the properties of random deterministic automata (including random generation and analysis of algorithms), with an emphasis on their typical algebraic properties.

 

Nicolas Ollinger

The periodicity problem of cellular automata

(joint work with J. Kari, A. Gajardo, and R. Torres)

The periodicity problem of cellular automata, to decide whether every orbit of a given cellular automaton is periodic, is related to the finiteness problem of Mealy machines in the following way: the finiteness problem for reset Mealy machines is decidable if and only if the periodicity problem is decidable for one-sided cellular automata. In this talk, we present the undecidability of the periodicity problem for cellular automata (in the general setting), its relation with both immortality of periodicity problems for counter machines and Turing machines. We investigate the problem of the existence of a periodic configuration for complete reversible Turing machines and exhibit a small Turing machine with interesting properties: the so-called SMART machine.

 

Dmytro Savchuk

Duality in reversible automata generating lamplighter type groups
 
We study a class of groups generated by reversible automata modeling multiplication in the ring of formal power series. The realization of the lamplighter type groups by similar types of automata has been studied by several authors since the beginning of 2000’s. We show that in many cases the group generated by the dual automaton is again of lamplighter type and that it also acts on series in certain rational function. This is a joint work with Ievgen Bondarenko.

 

Reem Yassawi
 
Linear cellular automata and p-automatic sequences
 
Let p be prime. We study the links between p-automatic sequences and asymptotic properties of linear cellular automata, emphasizing the constructive aspect. In particular, we outline a method that aims to identify nontrivial measures that are invariant under the action of both the shift and the cellular automaton under study. This is joint work with Benjamin Hellouin and Eric Rowland.
 
e
Personnes connectées : 1