<p>Take a look at <a href="http://www.cs.huji.ac.il/~yonatanm/publications/PrimeLanguages.pdf">this MFCS 2013 paper</a>, which studies compositionality in automata. Perhaps it will help.</p>

CC BY-SA 3.0
2016-06-06T05:32:06.813Z
+1 for the link. Quoting from the discussion of the article, _While the general case is still open_, it seems that the article only explores the permutation automata case. Are there any more recent development for general cases? I mean in the sense of  cartesian product? (Krohn-Rhodes theory deals with wreath product) Thanks.
Nobody
CC BY-SA 3.0
2016-06-06T06:04:25.157Z
I don't know of any recent developments. I can tell you that there was no direct follow-up work to this paper.
But this can serve as an indication that the problem is indeed not easy.
Shaull
CC BY-SA 3.0
2016-06-05T06:11:56.590Z
2016-06-05T06:11:56.590Z
Shaull
<p>Lets give some obvious way to recover one "factor" of the product automaton. If $\mathcal A_i = (Q_i, \delta_i, q_{0i}, F_i), i = 1,2$ and $\mathcal A = \mathcal A_1 \times \mathcal A_2$ denotes the product automaton, then if we define
$$
 \pi_1( (q, q') ) := q
$$
i.e. just forgeting about $\mathcal A_2$, or projecting onto the second component, we have $Q_1 = \pi(Q_1\times Q_2)$, also if we want to know $\delta_1(q,x)$ pick some $q' \in Q_2$ and compute in the product automaton $\pi((\delta_1(q,x), \delta_2(q', x)) = \delta_1(q,x)$, hence we can also recover the transition in $\mathcal A_1$.</p>

<p>So if we know that an automaton is a cartesian (or external) product automaton, we can recover the factors easily.</p>

<p>But I guess this is not what you have in mind regarding your other questions. Two questions arise here (in the following by automaton isomorphism I mean isomorphic as state graph, i.e. with no respect to initial or final states, as you said the language is not so much a concern here):</p>

<p>1) Given any automaton that is isomorphic to a product automaton (i.e. could be decomposed in some way) of some finite number of automata, is this decomposition essentially unique? (given that the factors could not be decomposed further, for otherwise obviously not). More presicely if
$$
 \mathcal A_1 \times \ldots \times \mathcal A_k \cong \mathcal B_1 \times \ldots \times \mathcal B_l
$$
for indecomposable automata $\mathcal A_i, \mathcal B_j$ does this imply $k = l$ and $\mathcal A_i \cong \mathcal B_{\pi(i)}$ for some reordering $\pi : \{1,\ldots k \}\to \{1,\ldots k \}$. I conjecture that to be true, but I have no proof yet.</p>

<p>2) Given any two automata $\mathcal A, \mathcal B$, does there exists a third automaton $\mathcal C$ such that $\mathcal A = \mathcal B \times \mathcal C$.</p>

<p>It is easy to derive necessary conditions for that to be the case, but I do not see any easy sufficient criterions for some automaton to be a factor of another.</p>

<p>But lets generalise our initial example slightly, note that
$$
 \pi_1( (\delta_1(q, x), \delta_2(q', x)) = \delta_1(q,x)
                                          = \delta_1(\pi_1(q,q'), x)
$$
for all $q \in Q_1, q' \in Q_2$ and hence $\pi$ is a state graph homomorphism of $\mathcal A_1 \times \mathcal A_2$ onto $\mathcal A_2$. So we define:</p>

<blockquote>
  <p>An automaton $\mathcal A$ <em>divides</em> an automaton $\mathcal B$ if there exists a state graph homomorphism $\mathcal B$ onto $\mathcal A$.</p>
</blockquote>

<p>Really interesting gets this notion if we consider the transition monoids of the automata, then this definition is equivalent to that there exists a surjective homomorphism from the transition monoid of $\mathcal B$ to that of $\mathcal A$.</p>

<p>More generally, we say that a monoid $M$ divides a monoid $N$ if $M$ is the image of some morphism from a submonoid of $N$. And this notion is widely used, and given the relation between DEA and finite monoids closely related to you question on the decomposition of automata. If you want to find out more, check out these resources:</p>

<p><a href="http://arxiv.org/abs/1011.6491" rel="nofollow">H. Straubing, P. Weil</a> An introduction to finite automata and their connection to logic,</p>

<p><a href="https://www.irif.univ-paris-diderot.fr/~jep/MPRI/MPRI.html" rel="nofollow">Course website</a> with lots of information.</p>

<p><em>Remark</em>: There is also another notion of "<em>quotienting</em>", see <a href="https://en.wikipedia.org/wiki/Quotient_automaton" rel="nofollow">wikipedia:quotient automaton</a>, but this is just a rule for collapsing states and used in learning/language inference algorithms or state minimization.</p>

CC BY-SA 3.0
2016-06-13T18:19:41.997Z
2016-06-14T09:14:39.497Z
2016-06-14T09:14:39.497Z
StefanH
<p><strong>Background:</strong></p>

<p>Given two deterministic finite automata A and B, we form the product C by letting the states in C be the cartesian product of states in A and states in B. Then, we choose transitions, initial state, and final states so the language accepted by C is the intersection of the languages for A and B.</p>

<p><strong>Questions:</strong></p>

<p>(1) Can we "divide" C by B to find A? Is A even unique, up to isomorphism? We care about the state diagrams, not the languages here and below. Thus, we don't allow compressing the state diagrams to reduce the number of states.</p>

<p>(2) If A is unique, is there an efficient algorithm to find it?</p>

<p>(3) Does every deterministic finite automaton have a unique factorization into "primes". A prime here means an automaton that cannot be factored, that is, written as a product of 2 smaller automata.</p>

<ul>
<li>Work with @MichaelWehar</li>
</ul>

CC BY-SA 3.0
2016-06-05T21:38:29.053Z
Consider Brzozowski derivatives. https://en.wikipedia.org/wiki/Brzozowski_derivative
Vijay D
CC BY-SA 3.0
2016-06-06T05:36:52.540Z
@halfTrucker Krohn-Rhodes theory deals with wreath product. The OP is asking about Cartesian product.
Nobody
CC BY-SA 3.0
2016-06-07T17:06:30.953Z
Thanks @halfTrucker, this is really interesting! As scaaahu says, I'm looking for cartesian product, but your reference is still great.
Whosyourjay
<fl.formal-languages><automata-theory><dfa>
Is there a well-defined division operation on finite automata?
Whosyourjay
# Is there a well-defined division operation on finite automata?

(Asked by: username_0 on 2016-06-04)

**Background:**

Given two deterministic finite automata A and B, we form the product C by letting the states in C be the cartesian product of states in A and states in B. Then, we choose transitions, initial state, and final states so the language accepted by C is the intersection of the languages for A and B.

**Questions:**

(1) Can we "divide" C by B to find A? Is A even unique, up to isomorphism? We care about the state diagrams, not the languages here and below. Thus, we don't allow compressing the state diagrams to reduce the number of states.

(2) If A is unique, is there an efficient algorithm to find it?

(3) Does every deterministic finite automaton have a unique factorization into "primes". A prime here means an automaton that cannot be factored, that is, written as a product of 2 smaller automata.

* Work with @MichaelWehar

**Tags:** fl.formal-languages, automata-theory, dfa

> **Comments:**
> **username_1**: Consider Brzozowski derivatives. https://en.wikipedia.org/wiki/Brzozowski_derivative  
> **username_2**: @halfTrucker Krohn-Rhodes theory deals with wreath product. The OP is asking about Cartesian product.  
> **username_0**: Thanks @halfTrucker, this is really interesting! As scaaahu says, I'm looking for cartesian product, but your reference is still great.  

---

## 2 answers

### Answer by username_3 on 2016-06-05. Score: 8

Take a look at [this MFCS 2013 paper](http://www.cs.huji.ac.il/~yonatanm/publications/PrimeLanguages.pdf), which studies compositionality in automata. Perhaps it will help.

> **Comments:**
> **username_2**: +1 for the link. Quoting from the discussion of the article, _While the general case is still open_, it seems that the article only explores the permutation automata case. Are there any more recent development for general cases? I mean in the sense of  cartesian product? (Krohn-Rhodes theory deals with wreath product) Thanks.  
> **username_3**: I don't know of any recent developments. I can tell you that there was no direct follow-up work to this paper. But this can serve as an indication that the problem is indeed not easy.  

---

### Answer by username_4 on 2016-06-13. Score: 4

Lets give some obvious way to recover one "factor" of the product automaton. If $\mathcal A\_i = (Q\_i, \delta\_i, q\_{0i}, F\_i), i = 1,2$ and $\mathcal A = \mathcal A\_1 \times \mathcal A\_2$ denotes the product automaton, then if we define
$$
\pi\_1( (q, q') ) := q
$$
i.e. just forgeting about $\mathcal A\_2$, or projecting onto the second component, we have $Q\_1 = \pi(Q\_1\times Q\_2)$, also if we want to know $\delta\_1(q,x)$ pick some $q' \in Q\_2$ and compute in the product automaton $\pi((\delta\_1(q,x), \delta\_2(q', x)) = \delta\_1(q,x)$, hence we can also recover the transition in $\mathcal A\_1$.

So if we know that an automaton is a cartesian (or external) product automaton, we can recover the factors easily.

But I guess this is not what you have in mind regarding your other questions. Two questions arise here (in the following by automaton isomorphism I mean isomorphic as state graph, i.e. with no respect to initial or final states, as you said the language is not so much a concern here):

1) Given any automaton that is isomorphic to a product automaton (i.e. could be decomposed in some way) of some finite number of automata, is this decomposition essentially unique? (given that the factors could not be decomposed further, for otherwise obviously not). More presicely if
$$
\mathcal A\_1 \times \ldots \times \mathcal A\_k \cong \mathcal B\_1 \times \ldots \times \mathcal B\_l
$$
for indecomposable automata $\mathcal A\_i, \mathcal B\_j$ does this imply $k = l$ and $\mathcal A\_i \cong \mathcal B\_{\pi(i)}$ for some reordering $\pi : \{1,\ldots k \}\to \{1,\ldots k \}$. I conjecture that to be true, but I have no proof yet.

2) Given any two automata $\mathcal A, \mathcal B$, does there exists a third automaton $\mathcal C$ such that $\mathcal A = \mathcal B \times \mathcal C$.

It is easy to derive necessary conditions for that to be the case, but I do not see any easy sufficient criterions for some automaton to be a factor of another.

But lets generalise our initial example slightly, note that
$$
\pi\_1( (\delta\_1(q, x), \delta\_2(q', x)) = \delta\_1(q,x)
= \delta\_1(\pi\_1(q,q'), x)
$$
for all $q \in Q\_1, q' \in Q\_2$ and hence $\pi$ is a state graph homomorphism of $\mathcal A\_1 \times \mathcal A\_2$ onto $\mathcal A\_2$. So we define:

> An automaton $\mathcal A$ *divides* an automaton $\mathcal B$ if there exists a state graph homomorphism $\mathcal B$ onto $\mathcal A$.

Really interesting gets this notion if we consider the transition monoids of the automata, then this definition is equivalent to that there exists a surjective homomorphism from the transition monoid of $\mathcal B$ to that of $\mathcal A$.

More generally, we say that a monoid $M$ divides a monoid $N$ if $M$ is the image of some morphism from a submonoid of $N$. And this notion is widely used, and given the relation between DEA and finite monoids closely related to you question on the decomposition of automata. If you want to find out more, check out these resources:

[H. Straubing, P. Weil](http://arxiv.org/abs/1011.6491) An introduction to finite automata and their connection to logic,

[Course website](https://www.irif.univ-paris-diderot.fr/~jep/MPRI/MPRI.html) with lots of information.

*Remark*: There is also another notion of "*quotienting*", see [wikipedia:quotient automaton](https://en.wikipedia.org/wiki/Quotient_automaton), but this is just a rule for collapsing states and used in learning/language inference algorithms or state minimization.


---

