1
$\begingroup$

Acyclic DFAs recognize finite languages. For more info, see this Wikipedia page : https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton

To explain that the product of two DFAs $A$ and $B$ could lead to a result of size $O(|A|.|B|)$ in the worst case, most examples make use of DFAs containing cycles (those cycles are responsible in creating |A| copies of B in the result) like in this example :

Product of two DFAs

As they are much more simpler than standard DFAs, I am wondering if the product operation (and more specifically union/intersection operations) of two acyclic DFAs $A$ and $B$ could result in a DFA of size $O(|A| + |B|)$ in the worst case ?

According to the article "State Complexity of Union and Intersection of Finite Languages" here : http://toc.yonsei.ac.kr/~emmous/papers/dlt07.pdf the authors say that the size of the DFA resulting from the product of two acyclic DFAs $A$ and $B$ remains in $O(|A|.|B|)$ only if the alphabet used is of variable size that depends on the size of the input DFAs. Thus, they conclude that this upper bound is $unreachable$ if the alphabet is of fixed size.

Does it mean that given a fixed size alphabet (e.g. $\sum=\{a,b\}$) and two DFAs $A$ and $B$ defined on $\sum$ , there is still the possibility that the intersection of $A$ and $B$ could result in a DFA of size $O(|A| + |B|)$ in the worst case ?

I would appreciate any counter-example, proof or reference to a paper dealing with this problem.

Many thanks, Luz.

$\endgroup$
2
$\begingroup$

Lemma 4 and Lemma 8 in your paper show that even for a fixed size alphabet, there are infinitely many finite languages with minimal DFAs $A,B$ of sizes tending to infinity such that the minimal DFAs for the intersection and union languages has $\Omega(\min(|A|,|B|)^2)$ states.

$\endgroup$
  • $\begingroup$ Thank you ! I should have taken more time to read it... Do you know if there are some interesting classes of DFAs whose product is $O(|A|+|B|)$ ? $\endgroup$ – Luz Jan 25 '17 at 16:25
  • $\begingroup$ Unfortunately I'm not an expert in the area. Have you considered unary languages? $\endgroup$ – Yuval Filmus Jan 25 '17 at 16:27

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.