Decidability of membership in the fixed point of a rational relation

Question

Given a finite alphabet $\Sigma$, a non-deterministic finite-state transducer representing rational a relation $T \subseteq \wp(\Sigma^* \times \Sigma^*)$, a finite state machine representing a regular language $L \subseteq \Sigma^*$, and a word $w \in \Sigma^*$. Let $T(L)$ denote the image of $T$ over $L$, i.e., $\left\{ w' \in \Sigma^* \mid \exists w \in L. (w,w') \in T\right\}$. Let $\mu$ and $\nu$ respectively represent the least and greatest fixed point operators.

1. Is it decidable whether $w \in \mu Z. L \cup T(Z)$?
2. Is it decidable whether $w \in \nu Z. L \cap T(Z)$?
3. If questions 1 or 2 are answered in the negative, does this change in the special case where $T$ is expressible as a finite union of deterministic transducers, i.e., $\mid T\left(\left\{w\right\}\right)\mid$ is finite for all $w$?
4. Are these results different when dealing with ranked trees rather than words, i.e., $\Sigma$ is a ranked alphabet, $L$ a tree-regular language, and $w$ a ranked tree over $\Sigma$?

Answer 1

The answer to (1) is no, even for deterministic transducers. The reason is that we can encode configurations (tape contents + head position + machine state) of Turing machines into words such that the configuration changes made by any machine $M$ can be represented by a transducer $T_M$, and then decidability of (1) would imply decidability of the halting problem. In some more detail, this is how it works:

For simplicity, I assume that our Turing machines move left or right in each step, i.e. for any machine state $q\in Q$ and tape symbol $a\in \Sigma$, the action $\delta(q,a)$ performed in $q$ upon reading $a$ is either $(q',a',L)$ or $(q',a',R)$ for some $q',a'$. The alphabet $\Sigma$ contains the blank $\_$, and $\Pi:=\Sigma\setminus\{\_\}$. I also assume that the machine erases the tape before halting, and doesn't write any blanks otherwise - this is a straightforward modification to any given machine, and ensures that all halting configurations are encoded as the same word.

The encoding of a configuration is a word in $(\Sigma\cup Q)^*$ of the form $\_uqav\_$, delimited by blanks, where $q\in Q$ is the current state, $a\in\Sigma$ is the content of the cell under the head, and $u,v\in\Pi^*$ are the contents to the left and to the right, respectively. Due to the above restriction, a halting configuration is encoded as $\_q_e\_\_$, where $q_e$ is the halting state.

The transducer $T_M$ operates in several phases, using its state to temporarily store a symbol $b\in\Sigma$:

• It reads the leading $\_$ and sets $b:=\_$;

• It reads $v = v_1\dots v_k$, in each step outputting $b$ and setting $b$ to the current $v_j$ (if $v$ is empty, then $b$ is still $\_$ after this);

• It reads $q$ and $a$. Then if $\delta(q,a) = (q',a',L)$, it outputs $q'ba'$, otherwise ($\delta(q,a) = (q',a',R)$), it outputs $ba'q'$. It also remembers the move direction.

• It reads and outputs $w\_$, unless we moved left, $w$ is empty, and $a'=\_$ (to avoid extra trailing $\_$).

Then $T_M^k(\_q_0w\_)$ encodes the configuration of $M$ after $k$ steps on input $w$, and $\_q_e\_\_\in\mu Z.\{\_q_0w\_\}\cup T_M(Z)$ iff $M$ halts on $w$.