Cet exposé prend pour point de départ la conjecture de Ballier-Stein, qui affirme que le problème du domino sur le graphe de Cayley d'un groupe finiment engendré est décidable si et seulement si le groupe est virtuellement libre. Nous proposons une double ouverture : considérer d'une part des graphes arbitraires, et d'autre part s'intéresser à toutes les propriétés des orbites d'automates cellulaires exprimables en logique du premier ordre. Ce formalisme inclut le problème du domino et plusieurs de ses variantes, mais aussi des problèmes comme l'injectivité ou la surjectivité des automates cellulaires.
Nous présenterons deux résultats : d'une part, l'existence d'une propriété du premier ordre sur les orbites d'automates cellulaires qui est décidable sur un graphe de Cayley d'un groupe G finiment engendré si et seulement si G est virtuellement libre ; d'autre part, l'existence de graphes 4-réguliers contenant une grille infinie comme sous-graphe sur lesquels le problème du domino (resp. et ses variantes) est décidable alors que ses variantes (resp. une propriété du premier ordre sur les orbites d'AC) sont indécidables.