Résumés

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é

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