15
$\begingroup$

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
$\endgroup$
  • 5
    $\begingroup$ The classic decomposition is Krohn-Rhodes theory -- a lot to look at. $\endgroup$ – user39300 Jun 4 '16 at 21:19
  • 2
    $\begingroup$ Consider Brzozowski derivatives. en.wikipedia.org/wiki/Brzozowski_derivative $\endgroup$ – Vijay D Jun 5 '16 at 21:38
  • 2
    $\begingroup$ @halfTrucker Krohn-Rhodes theory deals with wreath product. The OP is asking about Cartesian product. $\endgroup$ – scaaahu Jun 6 '16 at 5:36
  • 2
    $\begingroup$ Thanks @halfTrucker, this is really interesting! As scaaahu says, I'm looking for cartesian product, but your reference is still great. $\endgroup$ – Whosyourjay Jun 7 '16 at 17:06
8
$\begingroup$

Take a look at this MFCS 2013 paper, which studies compositionality in automata. Perhaps it will help.

$\endgroup$
  • 2
    $\begingroup$ +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. $\endgroup$ – scaaahu Jun 6 '16 at 5:32
  • 3
    $\begingroup$ 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. $\endgroup$ – Shaull Jun 6 '16 at 6:04
4
$\begingroup$

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 An introduction to finite automata and their connection to logic,

Course website with lots of information.

Remark: There is also another notion of "quotienting", see wikipedia:quotient automaton, but this is just a rule for collapsing states and used in learning/language inference algorithms or state minimization.

$\endgroup$

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.