Que signifie réellement le problème de pré-image des automates cellulaires?

Question

Je lis sur les automates cellulaires et la complexité de calcul et j'ai trouvé un article connexe de F. Green, Problèmes NP-Complete dans les automates cellulaires.

Dans la 2e page, il répertorie trois problèmes complets NP liés à CA, le premier problème est:

CA Preimage: Compte tenu d'une sous-configuration de la longueur $ k $, y a-t-il une configuration qui aurait pu le conduire en pas de temps $ k $?

Je suis confondu avec le terme "sous-configuration" et sa signification, dans l'article, il déclare qu'une sous-configuration est États contagieux dans un tableau fini.

1- Cela signifie-t-il une structure comme la règle 110 ou 90 - ECA en longueur $ k $?

2- Ou cela signifie-t-il un modèle généré après un pas de temps $ k $ dans une structure spécifique (c'est-à-dire un modèle dans la règle 110)?

3- Pourquoi le problème indique que la longueur de la sous-configuration devrait être égale aux étapes de temps dans lesquelles il a été généré? Et si le problème était résoluble en pas de temps de K $ mais avec des pas de temps constants $ z $?