Given two DFAs $A$ and $B$ defined on the same alphabet, a (graph) homomorphism $h:A \rightarrow B$ from $A$ to $B$ is a mapping of the states of $A$ into the states of $B$ such that :
- if the state $x$ is initial (resp. final) in $A$ then $h(x)$ is initial (resp. final) in $B$
- if there is a $\lambda$-transition from the state $x$ to the state $y$ in $A$ then it is also the case from $h(x)$ to $h(y)$ in $B$
Let $A$ and $B$ be two DFAs and $L_A$ and $L_B$ their respective languages, if there exists a (graph) homomorphism from $A$ to $B$ then $L_A \subseteq L_B$. But the converse does not necessarily hold.
My question : What are the requirements on $A$ and $B$ to get the equivalence between (graph) homomorphism and language containment ? And if the equivalence is possible, what are the properties of such (graph) homomorphism ?
I conjecture that we get the equivalence with the minimality of both automata : if $A$ and $B$ are minimal then there exists a (graph) homomorphism from $A$ to $B$ iff $L_A \subseteq L_B$.
I also suspect this (graph) homomorphism $h:A \rightarrow B$ to be unique. Indeed, because of the determinism, any path in $A$ can be found only once in $B$.
I found very few informations (papers, lecture notes, books, tutorials) about this relationship between (graph) homomorphism and language containment and I would really appreciate any references or any answers regarding this problem.
Thank you very much, Luz :-)