7
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ – András Salamon Apr 19 '17 at 14:28
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 19 '17 at 15:53
  • $\begingroup$ 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. $\endgroup$ – Luz Apr 19 '17 at 18:15
  • $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Apr 20 '17 at 12:08
  • $\begingroup$ 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 $\endgroup$ – Luz Apr 20 '17 at 13:14
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 19 '17 at 15:50
  • $\begingroup$ ah indeed, I add a small edit to clarify $\endgroup$ – Denis Apr 19 '17 at 15:55
  • $\begingroup$ 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. $\endgroup$ – Luz Apr 20 '17 at 15:09

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.