Разрешима ли эта задача (про перезапись слов)?

[AGu]

Рассмотрим какой-нибудь алфавит $A$ и функцию $f:E\to A^+$,
определенную на конечном подмножестве $E\subset A^+$.

Продолжим $f$ на $D=\{ea :\ e\in E,\ a\in A^*\}$, полагая $f(ea)=f(e)a$,
где $e$ -- самый длинный префикс слова $ea$, принадлежащий $E$.

Положим ${\rm dom}\,f^\infty = \{x\in D : (\forall\,n\in\mathbb N)\ f^n(x)\in D\}$.
Т. е. ${\rm dom}\,f^\infty$ -- это множество бесконечно переписываемых слов:
$x\in D,\ f(x)\in D,\ f(f(x))\in D,\ \dots$

Существует ли алгоритм, который для данных $f$ и $x\in A^+$
выясняет принадлежность $x\in{\rm dom}\,f^\infty$ ?

P.S. Ответ я знаю, но я его получил муторным кустарным способом.
Не сводится ли эта задача к чему-нибудь хорошо известному?