Эффективная конкатенация ДФА?

Существует теоретическое доказательство того, что наивная декартова конструкция продукта для пересечения DFAs - «лучшее, что мы можем сделать». А как насчет объединения двух DFA? Тривиальная конструкция включает в себя преобразование каждого DFA в NFA, добавление эпсилон-перехода и определение результирующего NFA. Можем ли мы сделать лучше? Существует ли известная граница для размера DFA с минимальной конкатенацией (в терминах размеров DFA с "префиксом" и "суффиксом")?

Да - известно, что существуют DFA с и n состояниями, соответственно, так что минимальный DFA для объединения соответствующих языков имеет m * 2 n - 2 n - 1 состояний, что соответствует известной верхней границе.$m$$n$$m*2^n - 2^{n-1}$

Впервые это было замечено Масловым в 1970 году и вновь открыто Ю, Чжуаном и К. Саломаа в их работе «Сложность состояний некоторых основных операций на обычных языках», TCS 125 (1994), 315-328.