<p>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)$.</p>

<p>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.</p>

<p>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. </p>

<p>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.</p>

<p>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)$.</p>

<p>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.</p>

CC BY-SA 3.0
2017-04-19T15:50:37.567Z
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
CC BY-SA 3.0
2017-04-19T15:55:31.677Z
ah indeed, I add a small edit to clarify
Denis
CC BY-SA 3.0
2017-04-20T15:09:09.200Z
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
CC BY-SA 3.0
2017-04-19T15:46:39.523Z
2017-04-20T00:14:07.637Z
2017-04-20T00:14:07.637Z
Denis
<p>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 :</p>

<ul>
<li>if the state $x$ is initial (resp. final) in $A$ then $h(x)$ is initial (resp. final) in $B$</li>
<li>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$</li>
</ul>

<p>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.</p>

<p><strong>My question</strong> : 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 ?</p>

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

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

<p>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.</p>

<p>Thank you very much, Luz :-)</p>

CC BY-SA 3.0
2017-04-19T14:28:59.053Z
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
CC BY-SA 3.0
2017-04-19T15:53:40.167Z
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
CC BY-SA 3.0
2017-04-19T18:15:31.953Z
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
CC BY-SA 3.0
2017-04-20T12:08:42.607Z
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
CC BY-SA 3.0
2017-04-20T13:14:26.293Z
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 : https://en.wikipedia.org/wiki/Trie
Luz
CC BY-SA 3.0
2017-04-20T14:25:49.543Z
Given two DFA $A$ and $B$, let $m_B$ be the minimal form of $B$ and let $M^A$ be the "maximal" form of $A$. As all words are final states in $M^A$, $M^A$ is an infinite tree since the paths accepting those words share their common prefixes. If a word $w$ from $L_A$ is accepted by $B$ there is an elementary homomorphism of the path in $M^A$ accepting $w$ into an accepting path of $m_B$. We can build the whole homomorphism $M^A \rightarrow m_B$ by joining all together the previous elementary homomorphisms from each path of $M^A$ into $m_B$. Thus, $M^A \rightarrow m_B$ iff $L_A \subseteq L_B$.
Luz
CC BY-SA 3.0
2017-04-20T14:29:11.633Z
Now, building $M^A$ by creating as many final states as there are words in $L_A$ (thus an infinity), is sufficient to ensure the equivalence $M^A \rightarrow m_B$ iff $L_A \subseteq L_B$. But it is necessary ? We could think about a process that given $A$ and $B$, iteratively expand $A$ into a form $A'$ that gets closer to $M^A$ at each step of the iteration, while keeping it finite. And this iteration would stop either when $A' \rightarrow m_B$ holds or else when $A'$ has become sufficiently large to say that for every next steps $A' \rightarrow m_B$ will never hold.
Luz
CC BY-SA 3.0
2017-04-20T14:48:45.633Z
That is what I was trying to define in the former comment : an unravelling process of $A$ into a tree-shaped DFA $A'$ that allows looping transitions from a node of a branch to one of its ancestor (when the language is infinite) and whose maximum height is $2|B|$ (the unravelling process stops when the size of every branches of $A'$ reaches $2|B|$ and no homomorphism has been found so far).
Luz
<graph-theory><automata-theory><regular-language><dfa><homomorphism>
Automata : Language Containment, Minimality & Graph Homomorphism
Luz
# Automata : Language Containment, Minimality & Graph Homomorphism

(Asked by: username_0 on 2017-04-19)

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

**Tags:** graph-theory, automata-theory, regular-language, dfa, homomorphism
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_2**: 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$.  
> **username_0**: 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 : https://en.wikipedia.org/wiki/Trie  
> **username_0**: Given two DFA $A$ and $B$, let $m_B$ be the minimal form of $B$ and let $M^A$ be the "maximal" form of $A$. As all words are final states in $M^A$, $M^A$ is an infinite tree since the paths accepting those words share their common prefixes. If a word $w$ from $L_A$ is accepted by $B$ there is an elementary homomorphism of the path in $M^A$ accepting $w$ into an accepting path of $m_B$. We can build the whole homomorphism $M^A \rightarrow m_B$ by joining all together the previous elementary homomorphisms from each path of $M^A$ into $m_B$. Thus, $M^A \rightarrow m_B$ iff $L_A \subseteq L_B$.  
> **username_0**: Now, building $M^A$ by creating as many final states as there are words in $L_A$ (thus an infinity), is sufficient to ensure the equivalence $M^A \rightarrow m_B$ iff $L_A \subseteq L_B$. But it is necessary ? We could think about a process that given $A$ and $B$, iteratively expand $A$ into a form $A'$ that gets closer to $M^A$ at each step of the iteration, while keeping it finite. And this iteration would stop either when $A' \rightarrow m_B$ holds or else when $A'$ has become sufficiently large to say that for every next steps $A' \rightarrow m_B$ will never hold.  
> **username_0**: That is what I was trying to define in the former comment : an unravelling process of $A$ into a tree-shaped DFA $A'$ that allows looping transitions from a node of a branch to one of its ancestor (when the language is infinite) and whose maximum height is $2|B|$ (the unravelling process stops when the size of every branches of $A'$ reaches $2|B|$ and no homomorphism has been found so far).  

---

## 1 answers

### Answer by username_3 on 2017-04-19. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  
> **username_3**: ah indeed, I add a small edit to clarify  
> **username_0**: 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.  

---

