Concatenação eficiente de DFAs?

Há evidências teóricas de que a construção ingênua de produto cartesiano para a interseção de DFAs é "o melhor que podemos fazer". E a concatenação de dois DFAs? A construção trivial envolve a conversão de cada DFA em um NFA, adicionando uma transição épsilon e determinando o NFA resultante. Podemos fazer melhor? Existe um limite conhecido no tamanho do DFA de concatenação mínima (em termos de tamanhos dos DFAs "prefixo" e "sufixo")?

Sim - sabe-se que existem DFA de e n estados, respectivamente, de modo que o DFA mínimo para a concatenação dos idiomas correspondentes tenha m ∗ 2 n - 2 n - 1 estados, o que corresponde ao limite superior conhecido.$m$$n$$m*2^n - 2^{n-1}$

Isso foi observado pela primeira vez por Maslov em 1970 e redescoberto por Yu, Zhuang e K. Salomaa em seu artigo "As complexidades estatais de algumas operações básicas em línguas regulares", TCS 125 (1994), 315-328.