<p>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:</p>

<p>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.</p>

<p>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.</p>

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

<ul>
<li><p>It reads the leading $\_$ and sets $b:=\_$;</p></li>
<li><p>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);</p></li>
<li><p>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.</p></li>
<li><p>It reads and outputs $w\_$, unless we moved left, $w$ is empty, and $a'=\_$ (to avoid extra trailing $\_$).</p></li>
</ul>

<p>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$. </p>

CC BY-SA 3.0
2015-05-09T21:41:57.367Z
2015-05-09T21:41:57.367Z
Klaus Draeger
<p>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.</p>

<ol>
<li>Is it decidable whether $w \in \mu Z. L \cup T(Z)$?</li>
<li>Is it decidable whether $w \in \nu Z. L \cap T(Z)$?</li>
<li>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$?</li>
<li>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$?</li>
</ol>

<automata-theory><model-checking>
Decidability of membership in the fixed point of a rational relation
Daniel Franke
# Decidability of membership in the fixed point of a rational relation

(Asked by: username_0 on 2015-05-09)

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

**Tags:** automata-theory, model-checking

---

## 1 answers

### Answer by username_1 on 2015-05-09. Score: 4 | Accepted answer

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


---

