1
$\begingroup$

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.

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

Your processes are just deterministic finite-state transducers.

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

Question 2: You seem to be asking if we can minimize a deterministic finite-state transducer.

I don't know the answer to either of these questions -- they are very reasonable questions -- but hopefully this gives you some terminology you can search for.

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.

Regarding Question 2, Wikipedia claims that transducers can be minimized and gives a reference.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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