Compatibilité Verticale/Horizontale des Subshifts
1 : Equipe AMACC - Laboratoire GREYC - UMR6072
Université de Caen
On étudie la notion de compatibilité totale : étant donné deux subshifts unidimensionnels H et V, peut-on les réunir en un subshift de dimension 2 dont l'ensemble des lignes est H et l'ensemble des colonnes est V. On montre que ce problème est décidable quand H et V sont des nearest neighbour subshifts, mais que le problème devient indécidable dès que l'on autorise des instances légèrement plus complexes. On s'intéresse également à la généralisation du problème en dimension 3.