Fonctionne avec Indico
v3.2.9
Le groupe de l'allumeur de réverbères est $G=\mathbb Z/2 \wr \mathbb Z$; on s'intéresse aux sous-décalages de type fini sur $G$, qui sont les fermés $G$-invariants dans $\{1,\dots,d\}^G$ définis par un ensemble fini de mots interdits. Dualement, ce sont les $G$-algèbres booléenes de présentation finie.
Avec Ville Salo, on s'intéresse au "problème de domino sur des groupes": étant donnée une liste finie de mots interdits, le sous-décalage correspondant est-il vide, ou contient-il une configuration donnée? Dualement, l'algèbre est-elle triviale, ou son problème du mot est-il décidable?
On regarde en particulier le groupe de l'allumeur de réverbères car il est "entre" $\mathbb Z^2$ (et autres groupes contenant des plans) pour lesquels les problèmes sont indécidables, et les groupes libres pour lesquels ils sont décidables.
Je montrerai en particulier que le problème du mot est indécidable pour l'allumeur de réverbères.