Is O(|A| + |B|) the size of the union of two synchronized DFAs A and B?

In general, the size of the DFA resulting from the union of two DFAs A and B is O(|A|.|B|) in the worst case (usually the product construction is used to compute the union).

Let's consider the class of 'synchronized DFAs' as the class of DFAs having a synchronizing word : https://en.wikipedia.org/wiki/Synchronizing_word

After looking at some examples of synchronized DFAs A and B, it seems possible to always build a synchronized DFA for the UNION of A and B with a size O(|A| + |B|) in the worst case.

Does anybody have any information, proof or paper about the union of two synchronized DFAs in O(|A| + |B|) ?

Many thanks,
Luz

Your conjecture is wrong. Consider the following languages:

-
$L_1$ is the language of words over $\{a,b,c\}$ such that the number of $b$s after the last $a$ is a multiple of $x$.

-
$L_2$ is the language of words over $\{a,b,c\}$ such that the number of $c$s after the last $a$ is a multiple of $y$.

The minimal DFA of $L_1$ contains $x$ states, and that of $L_2$ contains $y$ states. Both DFAs have $a$ as a synchronizing word. The minimal DFA for $L_1\cup L_2$ contains $xy$ states (and also has $a$ as a synchronizing word).

StackExchange Computer Science Q#68738, answer score: 5