State Complexity of Multiple Concatenation

Jozef Jirásek, Galina Jirásková

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 significa…