# Automata : Language Containment, Minimality & Graph Homomorphism

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 :-)

• Minimal automata are sometimes defined in terms of quotients of morphisms, so this might be a restatement of some classic result. It might be worth consulting a draft of Jean-Éric Pin's Mathematical Foundations of Automata Theory textbook. – András Salamon Apr 19 '17 at 14:28
• Taking minimal automata is clear the optimal choice for $B$, but for $A$, it is the worst choice. (Consider e.g. when $A$ is the minimal automaton of the empty language, as in Denis’s answer.) You’d actually want $A$ to be a “maximal” automaton, but unfortunately, as much as this concept makes sense at all, it would be an infinite automaton. – Emil Jeřábek Apr 19 '17 at 15:53
• Thank you. If $L_A$ is a finite language, we can unravel $A$ into a "trie"-shaped (prefix tree) automata $A'$. If $L_A$ is infinite let all paths in $A'$ be of size at least $2|B|$ and add backward looping transitions from a node to an ancestor in the trie at a distance of at least $|B|$ nodes from the initial state (the root) in order to have $L_{A'}=L_A$ and to ensure the existence of an homomorphism $A' \rightarrow B$ iff $L_A \subseteq L_B$. Could $A'$ be this "maximal" automaton you are talking about ? I would be surprised that homomorphisms haven't been used to test language containment. – Luz Apr 19 '17 at 18:15
• I don’t know what “trie” means. What I meant by “maximal automaton” is just the dual of the definition of a minimal automaton: $A$ is maximal if for all automata $B$ such that $L_A=L_B$, there is a homomorphism from $A$ to $B$. I should also insist that all states are reachable. Such an automaton has to be infinite. I believe it is unique. It can be constructed by taking all words as nodes, with the empty word being initial, words from $L$ final, and the obvious transition function. What you write seems to be an approximation of this with a finite automaton that works against small enough $B$. – Emil Jeřábek Apr 20 '17 at 12:08
• A trie is not really an interesting mathematical concept... It is more a computer science concrete artefact... it is called digital tree or prefix tree also. More info here : en.wikipedia.org/wiki/Trie – Luz Apr 20 '17 at 13:14

For inclusion, using your condition that non-final states can be mapped to final states does not work. Consider for instance that $A$ is a rejecting sink $p_0$, and $B$ is the minimal automaton for any non-trivial language with a transition $q_0\to q$. Then no such morphism can exist, because we must have $h(p_0)=q_0$, but also $h(p_0)=q$ because of the second condition, although $L(A)\subseteq L(B)$.

If you add the condition that nonfinal states are mapped to nonfinal states, it corresponds to language equality. You actually just need $B$ to be minimal for the equivalence to hold, assuming all states of $A$ are reachable.

First, notice that the morphism is indeed unique, as you must map the initial state of $A$ to the initial state of $B$, and then the whole morphism (if it exists) is induced by your second condition, since all states of $A$ are reachable.

We can now prove the equivalence. First it is clear that if the morphism exists, then $L(A)=L(B)$, since accepting runs of $A$ are mapped to accepting runs of $B$ and vice-versa.

Conversely, assume that $L(A)=L(B)$, we have to show that the morphism $h$ exists. The only problem we could have when building $h$ in the forced way, is if two words $u,v$ lead to the same state in $A$ but two different states in $B$. Since $B$ is minimal this means $u^{-1}L(B)\neq v^{-1}L(B)$. But $u^{-1}L(A)=v^{-1}L(A)$ since both words reach the same state of $A$, we reach a contradiction with $L(A)=L(B)$.

As Andras Salamon mentioned, the minimal automaton is indeed defined as the DFA $B$ such that for any DFA $A$ for the same language, such a morphism $A\to B$ exists.

• The OP does not assume that nonfinal states are mapped to nonfinal states. That is, the question is actually about what you discuss in the last paragraph. – Emil Jeřábek Apr 19 '17 at 15:50
• ah indeed, I add a small edit to clarify – Denis Apr 19 '17 at 15:55
• Thank you for your answer. Thus, your "sink" counter example shows that if the minimality of $B$ is required, it appears that $A$ must not be "minimal" but rather "maximal", as said in Emil Jerabek comments above. – Luz Apr 20 '17 at 15:09