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~(n2+...+nk) and (1/2~(2k-2))n_12~(n2+...+nk) 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).
展开▼
