Size of intersection of two acyclic DFAs A and B is O(|A|+|B|)?

Question

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 :

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.

Answer 1

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.