---
abstract: 'In @DMS11b, we introduced the weakly synchronizing languages for probabilistic automata. In this report, we show that the emptiness problem of weakly synchronizing languages for probabilistic automata is undecidable. This implies that the decidability result of @DMS11b [@tech; @DMS11] for the emptiness problem of weakly synchronizing language is incorrect.'
author:
- Laurent Doyen
- Thierry Massart
- Mahsa Shirmohammadi
bibliography:
- 'biblio.bib'
title: 'Infinite Synchronizing Words for Probabilistic Automata (Erratum)'
---

Definitions.
============

We present the main notations and definitions. We refer to @DMS11b for detailed preliminaries.

A *probability distribution* over a finite set $S$ is a function $d : S \rightarrow [0, 1]$ such that $\sum_{s \in S}
d(s)= 1$. The *support* of $d$ is the set ${{\sf Supp}}(d) = \{s \in
S \mid d(s) > 0\}$. We denote by ${{\cal D}}(S)$ the set of all probability distributions over $S$. Given a finite alphabet $\Sigma$, we denote by $\Sigma^{*}$ the set of all finite words and by $\Sigma^{\omega}$ the set of all infinite words over $\Sigma$. The length of a finite word $w$ is denoted by $\abs{w}$.

#### <span>**Probabilistic Automata.**</span>

A *probabilistic automaton* (PA) ${{\cal A}}= {\langle Q,\mu_{0},\Sigma,\delta \rangle}$ consists of a finite set $Q$ of states, an initial probability distribution $\mu_0 \in {{\cal D}}(Q)$, a finite alphabet $\Sigma$, and a probabilistic transition function $\delta: Q \times \Sigma \to {{\cal D}}(Q)$. In a state $q \in
Q$, the probability to go to a state $q' \in Q$ after reading a letter $\sigma \in \Sigma$ is $\delta(q,\sigma)(q')$. We define ${{\sf Post}}_{{{\cal A}}}(q,\sigma) = {{\sf Supp}}(\delta(q,\sigma))$, and for sets $s\subseteq Q$ and $\Sigma' \subseteq \Sigma$, let ${{\sf Post}}_{{{\cal A}}}(s,\Sigma')= \bigcup_{q \in s} \bigcup_{\sigma \in \Sigma'}  {{\sf Post}}_{{{\cal A}}}(q,\sigma)$. The *outcome* of ${{\cal A}}$ on an infinite word $w = \sigma_0 \sigma_1
\cdots$ is the infinite sequence ${{\cal A}}^{w}_{0} {{\cal A}}^{w}_{1} \dots $ of probability distributions ${{\cal A}}^{w}_i \in {{\cal D}}(Q)$ such that ${{\cal A}}^{w}_{0} =
\mu_{0}$ is the initial distribution, and for all $n > 0$ and $q
\in Q$, $$\textstyle {{\cal A}}^{w}_{n}(q) = \sum_{q' \in Q} {{\cal A}}^{w}_{n-1}(q') \cdot \delta(q',\sigma_{n-1})(q)$$ The *norm* of a probability distribution $X$ over $Q$ is $\norm{X} = \max_{q \in Q} X(q)$.

#### <span>**Weakly Synchronizing Language for PAs.**</span>

An infinite word $w$ is said to be *weakly synchronizing* for PA ${{\cal A}}$, if $$\limsup_{n \to \infty} \; \norm{{{\cal A}}^{w}_{n}} = 1.$$ We denote by ${{\cal L}_W}({{\cal A}})$ the set of all weakly synchronizing words, named weakly synchronizing language, of ${{\cal A}}$. Given a PA ${{\cal A}}$, the *emptiness problem* of weakly synchronizing language asks whether ${{\cal L}_W}({{\cal A}})=\emptyset$.

The emptiness problem of weakly synchronizing languages for PAs is undecidable.
===============================================================================

Theorem \[teo:weakly-undecide\] states that the emptiness problem of weakly synchronizing languages for PAs is undecidable. To show that, we present a reduction from *the value 1 problem for PAs* which is undecidable @GO10, to our problem.

#### <span>**The value 1 problem for PAs.** </span>

Let ${{\cal A}}={\langle Q, \mu_0,\Sigma,\delta \rangle}$ be a PA with a single initial state $q_0$ where $\mu_0(q_0)=1$ and a set of accepting states $F \subseteq Q$. The value 1 problem considers finite words: the computation of ${{\cal A}}$ on the word $w=\sigma_0
\sigma_1 \cdots \sigma_{n-1}$ is the sequence ${{\cal A}}^{w}_0 {{\cal A}}^{w}_1 \cdots {{\cal A}}^{w}_n$ where ${{\cal A}}^{w}_0=\mu_0$ and ${{\cal A}}^{w}_{i+1}(q)=\sum_{q'\in
  Q}{{\cal A}}^{w}_{i}(q')\delta(q',\sigma_{i})(q)$ for all $0 \leq i < n $. The <span>*<span>acceptance probability of $w$ by ${{\cal A}}$</span>*</span> is given by $P_{{{\cal A}}}(w)=\sum_{q\in F}{{\cal A}}^{w}_n(q)$. The value of ${{\cal A}}$, denoted $val({{\cal A}})$, is the supremum acceptance probability $val({{\cal A}})=\sup_{w \in
  \Sigma^{*}}P_{{{\cal A}}}(w)$. Given a PA ${{\cal A}}$, the *value 1 problem* asks whether $val({{\cal A}})=1$. It is equivalent to check if there are some words accepted by ${{\cal A}}$ with probability arbitrarily close to 1.

\[teo:val1\] The value 1 problem for probabilistic automata is undecidable @GO10.

Undecidability result. {#undecidability-result. .unnumbered}
----------------------

\[teo:weakly-undecide\] The emptiness problem of weakly synchronizing languages for probabilistic automata is undecidable.

We present a proof using a reduction from the value 1 problem for PAs. Given a PA ${{\cal B}}={\langle Q_{{{\cal B}}}, (\mu_0)_{{{\cal B}}},\Sigma_{{{\cal B}}},\delta_{{{\cal B}}} \rangle}$ equipped with the single initial state $q_0$ and accepting states $F_{{{\cal B}}}\subseteq Q_{{{\cal B}}}$, we construct another PA ${{\cal C}}={\langle Q_{{{\cal C}}}, (\mu_0)_{{{\cal C}}},\Sigma_{{{\cal C}}},\delta_{{{\cal C}}} \rangle}$, such that $val({{\cal B}})=1$ iff ${{\cal L}_W}({{\cal C}})\neq \emptyset$.

First, from the PA ${{\cal B}}$ we construct another PA ${{\cal A}}={\langle Q, \mu_0,\Sigma,\delta \rangle}$ such that ${{\cal B}}$ has value 1 iff ${{\cal A}}$ does. The state space is extended, by adding two new states $q_f$ and $q_n$ ($Q=Q_{{{\cal B}}} \cup \{q_f,q_n\}$). The alphabet $\Sigma=\Sigma_{{{\cal B}}} \cup \{ {\symbol{36}}\}$ where ${\symbol{36}}\not \in \Sigma_{{{\cal B}}}$. The initial state $q_0$ is in common, but only $q_f$ is an accepting state ($F=\{q_f\}$). The transition function globally remains unchanged; only the following transitions are added in ${{\cal A}}$: $\delta(q,{\symbol{36}})(q_f)=1$ for all $q \in F_1$, and $\delta(q,{\symbol{36}})(q_n)=1$ for all $q \in Q_{{{\cal B}}}\setminus F_1$. In addition, $\delta(q_f,\sigma)(q_n)=\delta(q_n,\sigma)(q_n)=1$ for all $\sigma \in \Sigma$.  \[fig:oneaccepting\] illustrates the definition of ${{\cal A}}$ from ${{\cal B}}$. By construction, since $q_f$ is the only accepting state and is only reachable with ${\symbol{36}}$, and ${{\sf Post}}_{{{\cal A}}}(\{q_f,q_n\},\Sigma)=\{q_n\}$. We see that $P_{{{\cal A}}}(w)=P_{{{\cal B}}}(v)$ if $w=v {\symbol{36}}$ with $v \in \Sigma_{{{\cal B}}}^{*}$, otherwise $P_{{{\cal A}}}(w)=0$. Thus, $A$ has value 1 iff ${{\cal B}}$ has value 1.

Then from the PA ${{\cal A}}$, we construct a PA ${{\cal C}}={\langle Q_{{{\cal C}}}, (\mu_0)_{{{\cal C}}},\Sigma_{{{\cal C}}},\delta_{{{\cal C}}} \rangle}$ such that ${{\cal L}_W}({{\cal C}})$, the weakly synchronizing language of ${{\cal C}}$ is not empty, iff ${{\cal A}}$ has value 1. For each state $q \in Q$ except $q_f$, a twin state ${\hat{ q}}$ is added to the state space. Thus, $Q_{{{\cal C}}}=Q\cup \{{\hat{ q}}\mid q\in Q\setminus \{q_f\}\}$. The alphabet $\Sigma_{{{\cal C}}}=\Sigma \cup \{ \#  \}$ where $\# \not \in \Sigma$. The initial distribution is $(\mu_0)_{{{\cal C}}}(q_0)=(\mu_0)_{{{\cal C}}}({\hat{ q}}_0)=\frac{1}{2}$. The probabilistic transitions function is defined as follows.

-   $\delta_{{{\cal C}}}(q_1,\sigma)(q_2)=\delta_{{{\cal C}}}(q_1,\sigma)({\hat{ q}}_2)=\delta_{{{\cal C}}}({\hat{ q}}_1,\sigma)(q_2)=\delta_{{{\cal C}}}({\hat{ q}}_1,\sigma)({\hat{ q}}_2)=\frac{1}{2} ~ \delta(q_1,\sigma)(q_2)$ for all states $q_1,q_2 \in Q\setminus\{q_f\}$ and all $\sigma \in \Sigma$.

-   $\delta_{{{\cal C}}}(q,\sigma)(q_f)=\delta_{{{\cal C}}}({\hat{ q}},\sigma)(q_f)=\delta(q,\sigma)(q_f)$ for all states $q \in Q\setminus\{q_f\}$.

-   $\delta_{{{\cal C}}}(q_f,\sigma)(q_1)=\delta_{{{\cal C}}}(q_f,\sigma)({\hat{ q}}_1)=\frac{1}{2}~\delta(q_f,\sigma)(q_1)$ for all states $q \in Q\setminus\{q_f\}$ and all $\sigma \in \Sigma$.

-   In addition, $\delta_{{{\cal C}}}(q,\#)(q_0)=\delta_{{{\cal C}}}(q,\#)({\hat{ q}}_0)=\frac{1}{2}$ for all $q \in Q_{{{\cal C}}}$.

 \[fig:undec\] shows the construction. For convenience, a twin $q$ and ${\hat{ q}}$ are drawn in an oval;  \[fig:twin\] illustrates the transitions between two pairs of twin states where each pair is replaced with an oval. Intuitively, the PA ${{\cal C}}$ mimics the behavior of ${{\cal A}}$ where each state $q$ (except the accepting state $q_f$) shares the probability to be in $q$ with the twin ${\hat{ q}}$, in all steps $n\in {\mathbb N}$. Moreover, each $\#$ "resets" ${{\cal C}}$.

\[b\]<span>0.45</span>

\[b\]<span>0.45</span>

Let us shortly formalize two important and intuitive properties of ${{\cal C}}$ resulting from the construction.

<span>**Property $P_1$:**</span> Let $w \in \Sigma_{{{\cal C}}}^{\omega} $ be an infinite word containing the symbol $\#$ such that $w= v_1 \# v_2$ where $v_1\in \Sigma_{{{\cal C}}}^{*}$ and $v_2 \in \Sigma_{{{\cal C}}}^{\omega}$. Let ${{\cal C}}^{w}_{0}  {{\cal C}}^{w}_{1} \cdots $ be the outcome of ${{\cal C}}$ on the word $w$; and ${{\cal C}}^{v_2}_{0}  {{\cal C}}^{v_2}_{1} \cdots$ be the outcome on $v_2$. Since ${{\sf Post}}_{{{\cal C}}}(Q_{{{\cal C}}}, \#)=\{q_0,{\hat{ q}}_0\}$ with uniform distribution, on inputting the letter $\#$, the automaton ${{\cal C}}$ is reset to the initial distribution $(\mu_0)_{{{\cal C}}}$, and one may "forget" the prefix $v_1 \#$. Formally, for all $i \in {\mathbb N}$ and $q \in Q_{{{\cal C}}}$, $${{\cal C}}^{w}_{\abs{v_1}+1+i}(q)= {{\cal C}}^{v_2}_{i}(q).$$

<span>**Property $P_2$:**</span> For all words $w \in \Sigma_{{{\cal B}}}^{*}$, the computations of ${{\cal A}}$ and ${{\cal C}}$ on $w$ give

a)

:   ${{\cal C}}^{w}_{\abs{w}}(q)={{\cal C}}^{w}_{\abs{w}}({\hat{ q}})=\frac{1}{2}{{\cal A}}^{w}_{\abs{w}}(q)$ for all $q\in Q\setminus\{q_f\}$,

b)

:   ${{\cal C}}^{w}_{\abs{w}}(q_f)={{\cal A}}^{w}_{\abs{w}}(q_f)=0$.

Let us recall that ${\symbol{36}}, \# \not \in \Sigma_{{{\cal B}}}$. Property $P_2.b$ can easily be proved since $\mu_0(q_f)=(\mu_0)_{{{\cal C}}}(q_f)=0$ and no $\sigma-$labeled transition with $\sigma \in \Sigma_{{{\cal B}}}$ reaches $q_f$. We prove Property $P_2.a$ by induction on the length of $w$.

Base ($\abs{w}=0$): Let $w$ be the empty word $\epsilon$. By construction, we know the initial distribution for ${{\cal A}}$ is $\mu_0(q_0)=1$ and for ${{\cal C}}$ is $(\mu_0)_{{{\cal C}}}(q_0)=(\mu_0)_{{{\cal C}}}({\hat{ q}}_0)=\frac{1}{2}$.

Induction: Assume that the statement holds for all words $w'$ with $w' <i$. Let $w=w' \sigma$ where $w' \in  \Sigma_{{{\cal B}}}^{i-1}$ and $\sigma\in \Sigma_{{{\cal B}}}$. By definition, $ {{\cal C}}^{w}_{i}(q_1) = \sum_{q \in Q_{{{\cal C}}}} {{\cal C}}^{w}_{i-1}(q) \cdot \delta_{{{\cal C}}}(q,\sigma)(q_1)$ for $q_1\in Q\setminus\{q_f\}$. By induction hypothesis, since ${{\cal C}}^{w'}_{i-1}(q_2)={{\cal C}}^{w'}_{i-1}({\hat{ q}}_2)$ for $q_2\in Q\setminus\{q_f\}$, and since $\delta_{{{\cal C}}}(q_2,\sigma)(q_1)=\delta_{{{\cal C}}}({\hat{ q}}_2,\sigma)(q_1)$, we conclude $ {{\cal C}}^{w}_{i}(q_1) = 2 \sum_{q_2 \in Q} {{\cal C}}^{w}_{i-1}(q_2) \cdot \delta_{{{\cal C}}}(q_2,\sigma)(q_1)=
2 \sum_{q_2 \in Q} (\frac{1}{2} {{\cal A}}^{w}_{i-1}(q_2) )\cdot (\frac{1}{2} \delta(q_2,\sigma)(q_1))=\frac{1}{2} \sum_{q_2 \in Q} {{\cal A}}^{w}_{i-1}(q_2) \cdot \delta(q_2,\sigma)(q_1)=\frac{1}{2} {{\cal A}}^{w}_{i}(q_1)$. Similarly, we obtain $ {{\cal C}}^{w}_{i}({\hat{ q}}_1)=\frac{1}{2}{{\cal A}}^{w}_{i}(q_1)$.

Now, we show that ${{\cal L}_W}({{\cal C}})\neq \emptyset$ iff the PA ${{\cal A}}$ has value 1.

$\Leftarrow$ First, we assume that ${{\cal A}}$ has value 1. So, for all $\epsilon >0$, there exists a finite word $w \in \Sigma^*$ such that $P_{{{\cal A}}}(w)>1-\epsilon$. Let $w_i$ be such that $P_{{{\cal A}}}(w_i)>1-2^{-i}$ for all $i \geq 1$. We claim that the infinite word $v=(w_{i}\#)_{i \in {\mathbb N}}=w_{1} \# w_{2} \# w_{3} \#\cdots$ is a weakly synchronizing word for ${{\cal C}}$. Let ${{\cal C}}^{v}_0 {{\cal C}}^{v}_1 \cdots$ be the outcome of ${{\cal C}}$ on $v$. For $i> 1$, let $v_i=w_{1} \# \cdots \#   w_{i}$ be the prefix of $v$ which ends with $w_{i}$. Let $\abs{v_i}$ denote the length of $v_i$, then $\abs{v_i}=(i-1)+\sum_{j=1}^{i} \abs{w_{j}}.$ The last $\#$ of the prefix $v_{i}$ is located at $\abs{v_{i-1}}+1$ (for $i>1$). Thus, ${{\cal C}}^{v}_{\abs{v_{i-1}}+1}=(\mu_0)_{{{\cal C}}}$ which is the initial distribution of ${{\cal C}}$. By construction, ${{\cal C}}^{v}_{\abs{v_{i-1}}+1+\abs{w_i}}(q_f)= P_{{{\cal A}}}(w_i)$. Hence, $\norm{{{\cal C}}^{v}_{\abs{v_{i}}}}> 1- 2^{-i}$ and $\lim_{i \to \infty}\norm{{{\cal C}}^{v}_{\abs{v_{i}}}}=1$. It implies that $\limsup_{n \to \infty}\norm{{{\cal C}}^{v}_{n}}=1$. Hence $v$ is a weakly synchronizing word for ${{\cal C}}$, thus ${{\cal L}_W}({{\cal C}})\neq \emptyset$.

$\Rightarrow$ Now let us assume that ${{\cal L}_W}({{\cal C}})\neq \emptyset$. So, by definition there exists an infinite word $v=\sigma_0 \sigma_1 \sigma_2 \cdots$ such that $\limsup _{n \to \infty}\norm{{{\cal C}}^{v}_n}=1$. We claim that $v$ contains infinitely many $\#$. Towards contradiction, assume that there exists $n \in {\mathbb N}$ such that for all $i>n$, $\sigma_i \neq \#$.

Let ${{\cal C}}^{v}_{0}  {{\cal C}}^{v}_{1} \cdots$ be the outcome of ${{\cal C}}$ on $v$. There are two cases:

-   There exists $j > n$ such that $\sigma_j={\symbol{36}}$. Since ${{\sf Post}}_{{{\cal C}}}(Q_{{{\cal C}}}, {\symbol{36}})=\{q_f,q_n,{\hat{ q}}_n\}$ and ${{\sf Post}}_{{{\cal C}}}(\{q_f,q_n,{\hat{ q}}_n\}, \Sigma )=\{q_n,{\hat{ q}}_n\}$, we have ${{\cal C}}^{v}_{j+1+i}(q_n)={{\cal C}}^{v}_{j+1+i}({\hat{ q}}_n)=\frac{1}{2}$ for all $i \in {\mathbb N}$, a contradiction with the fact that $v$ is weakly synchronizing.

-   For all $j >n$ we have $\sigma_j \neq {\symbol{36}}$. Let $k$ be one position after the last $\#$ in $v$, or $k=0$ if there is no $\#$. For all $i\in {\mathbb N}$, let $v_i=\sigma_{k} \sigma_{k+1} \cdots \sigma_{k+i-1}$ be the subword starting at $k$ with length $i$; and let ${{\cal C}}^{v_i}_{0}  {{\cal C}}^{v_i}_{1} \cdots {{\cal C}}^{v_i}_{i}$ be the computation of ${{\cal C}}$ on the finite word $v_i$. By Properties $P_1$ and $P_2$, ${{\cal C}}^{v_i}_{i}(q)={{\cal C}}^{v_i}_{i}({\hat{ q}})={{\cal C}}^{v}_{k+i}(q)={{\cal C}}^{v}_{k+i}({\hat{ q}})$ for all $i\in {\mathbb N}$ and all $q\in Q\setminus\{q_f\}$ and ${{\cal C}}^{v}_{k+i}(q_f)=0$. This gives $\norm{{{\cal C}}^{v}_{n+i}} \leq \frac{1}{2}$, a contradiction.

Now, we claim that $v$ contains infinitely many ${\symbol{36}}$ too. Towards contradiction, assume that there exists $n \in {\mathbb N}$ such that for all $i>n$, $\sigma_i \neq {\symbol{36}}$. Let $k_0 k_1 k_2 \cdots$ be the sequence of all positions in $v$ after $n$ where $\sigma_{k_j}=\#$ ($j\in {\mathbb N}$) in increasing order ($k_{j+1}>k_j$). So, $k_j>n$ and $\sigma_i \neq \#$ for all $j \in {\mathbb N}$ and all $i\neq k_j$. Let $v_i=\sigma_{k_j}\sigma_{k_j+1} \cdots \sigma_{i}$ be the finite subword of $v$ between the positions $k_j$ and $i$ where $k_j\leq i<k_{j+1}$ for some $j\in{\mathbb N}$. We see that $v_i=\# w$ for some $w\in\Sigma_{{{\cal B}}}^{*}$. Let ${{\cal C}}^{v_i}_{0}  \cdots {{\cal C}}^{v_i}_{i-k_j}$ be the computation of ${{\cal C}}$ on $v_i$. By Properties $P_1$ and $P_2$, ${{\cal C}}^{v_i}_{i-k_j}(q)={{\cal C}}^{v_i}_{i-k_j}({\hat{ q}})={{\cal C}}^{v}_{i}(q)={{\cal C}}^{v}_{i}({\hat{ q}})$ for all $i>n$ and all $q\in Q\setminus \{q_f\}$, and also ${{\cal C}}^{v_i}_{i}(q_f)=0$. This gives $\norm{{{\cal C}}^{v}_{i}} \leq \frac{1}{2}$ for all $i>n$, a contradiction with the fact that $v$ is weakly synchronizing.

We showed that $v$ contains infinitely many $\#$ and ${\symbol{36}}$. Since $v$ is weakly synchronizing, for all $\epsilon>0$ there exists $m>0$ where $\norm{{{\cal C}}^{v}_m}>1-\epsilon$ (In fact, since $v$ is weakly synchronizing, for all $\epsilon>0$ for all $n>0$ there exists $m>n$ where $\norm{{{\cal C}}^{v}_m}>1-\epsilon$, but we do not need $n$ here). For fixed $\epsilon < \frac {1}{2}$, let $m>0$ be such that $\norm{{{\cal C}}^{v}_m}>1-\epsilon$. Let $k<m$ be one position after the last $\#$ before $\sigma_m$ (i.e., $\sigma_{k-1}=\#$), or $k=0$ if there is no $\#$ before $\sigma_m$. Let $w$ be the finite subword of $v$ starting from position $k$ to the position $m$. By Properties $P_1$ and $P_2$, ${{\cal C}}^{v}_{m-k}(q)={{\cal C}}^{v}_{m-k}({\hat{ q}}) \leq \frac{1}{2}$ for all $q\in Q\setminus \{q_f\}$. Therefore, since $\norm{{{\cal C}}^{v}_m}>1-\epsilon$, we have ${{\cal C}}^{v}_m(q_f)>1-\epsilon$ and $P_{{{\cal A}}}(w)>1-\epsilon$. Hence ${{\cal A}}$ has value 1.

{'source': 'arXiv_out/1206'}