We describe witnesses for the concatenation of k languages over an alphabet of k + 1 symbols with a significantly simpler proof then that from the literature. Then we use slightly modified Maslov's automata to get witnesses over a k-letter alphabet which solves an open problem stated by Caron et al. [2018, Fund. Inform. 160, 255-279]. We prove that for k = 3, the ternary alphabet is optimal. We also obtain lower bounds n_1-1 + (1/2~(2k-2))2~(n_2+…+n_k) and (1/2~(2k-2))n_12~(n_2+…+n_k) in the binary and ternary case, respectively. Finally, we show that an upper bound for unary cyclic languages is n_1n_k/d + n_1 + … + n_k - k+1 + d where n_1 ≤ … ≤ n_k and d = gcd(n_1,... ,n_k).
展开▼
