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.