# Find a transducer that maps a given deterministic process to another

Let $$S$$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $$\mathcal{A}$$ and $$n$$ hidden states, the description is given through the $$n\times n$$ transition matrices $$T^{(a)}$$ with elements $$T^{(a)}_{ij}=Pr(s_{t+1}=j,A_t=a|s_t=i)$$, which encode the probability of being in state $$i$$ and upon emitting symbol $$a$$ transitioning to state $$j$$. For example the process for generating the sequence $$...010101010101..$$ would have the representation $$T^{(0)}=\begin{pmatrix} 0 & 1 \\ 0 & 0 \\ \end{pmatrix}\,,\, \, T^{(1)}=\begin{pmatrix} 0 & 0 \\ 1 & 0 \\ \end{pmatrix}$$

One can also construct deterministic transducers, that is, input-dependent Hidden Markov Models that take a deterministic process to another deterministic process. The description is similarly given through input-dependent transition matrices $$T^{(b|a)}$$, with elements $$T^{(b|a)}_{ij}=Pr(s_{t+1}=j,B_t=a|s_t=i,A_t=a)$$. For example, a deterministic transducer with two states and input and output alphabets $$\{0,1\}$$ that either performs the identity or a bit flip could be represented as $$T^{(0|0)}=\begin{pmatrix} 1 & 0 \\ 0 & 0 \\ \end{pmatrix}\,,\, \, T^{(1|0)}=\begin{pmatrix} 0 & 0 \\ 0 & 1 \\ \end{pmatrix} \,,\, \, T^{(0|1)}=\begin{pmatrix} 0 & 0 \\ 1 & 0 \\ \end{pmatrix} \,,\, \, T^{(1|1)}=\begin{pmatrix} 0 & 1 \\ 0 & 0 \\ \end{pmatrix}$$ and would map the previous defined process of alternating zero and one to the process that generates $$...001100110011...$$. This process' description would be $$\hat{P}^{(0)}=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{pmatrix} \, \,\, \hat{P}^{(1)}=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$$ After these definitions and example, I am ready to state my questions.

Question 1: Given two known processes $$S$$ and $$P$$ how can one find a transducer that maps one to the other (in general there is no unique solution). More importantly, is there a way to construct a transducer with minimal amount of hidden states? Is there an algorithm to do any of these two tasks?

Question 2: Given a representation of process $$S$$ with a HMM with $$n$$ states, how can one find the representation that has minimal number of states? In other words, is there an algorithm that takes a process with $$n$$ states and generates another with $$m$$, such that $$m\leq n$$ and equality if and only if the original representation of the process is already minimal?

PS: I do not have a formal background in CS but only maths, so please forgive me if my notation is weird and I am lacking in knowledge of basic results.

• What do you mean by mapping one process to another? What is the definition of that?
– D.W.
Aug 20 at 6:10

Question 1: It sounds like you are asking, given two deterministc finite-state transducers $$S,P$$, can we find a deterministic finite-state transducer so that $$S \circ T = P$$.
Regarding Question 1, I believe you can find a non-deterministic finite-state transducer $$T$$ such that $$S \circ T = P$$. Basically, you use the product composition; $$T$$ tracks the sequence of states traversed by $$S$$, and simultaneously guesses the sequence of states traversed by $$P$$. Maybe you could construct such a non-deterministic transducer, then check whether it can be determinized.