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$?

1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.