Descriptional Complexity of the Languages KaL: Automata, Monoids and Varieties

Ondřej Klíma, Libor Polák

The first step when forming the polynomial hierarchies of languages is to consider languages of the form KaL where K and L are over a finite alphabet A and from a given variety V o…