2025/11/05 by Jirásek, Jozef, Jirásková, Galina
#68QXX #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2511.03814
We describe witness languages meeting the upper bound on the state complexity of the multiple concatenation of k regular languages over an alphabet of size k+1 with a significantly simpler proof than that in the literature. We also consider the case where some languages may be recognized by two-state automata. Then we show that one symbol can be saved, and we define witnesses for the multiple concatenation of k languages over a k-letter alphabet. This solves an open problem stated by Caron et al. [2018, Fundam. Inform. 160, 255--279]. We prove that for the concatenation of three languages, the ternary alphabet is optimal. We also show that a trivial upper bound on the state complexity of multiple concatenation is asymptotically tight for ternary languages, and that a lower bound remains exponential in the binary case. Finally, we obtain a tight upper bound for unary cyclic languages and languages recognized by unary automata that do not have final states in their tails.