On the complexity of decidable cases of the commutation problem of languages

We investigate the complexity of basic decidable cases of the commutation problem for languages: testing the equality XY=YX for two languages X and Y. We show that it varies from co-NEXPTIME complete through PSPACE complete and co-NP complete to deterministic polynomial time, when Y is an explicitly given finite language and X is given by a CF grammar generating a finite language, a nondeterministic finite automaton (or a regular expression), an acyclic nondeterministic finite automaton or an explicitly given finite language, respectively. Interestingly in most cases the complexity status does not change if instead of explicitly given finite Y we consider general Y of the same type as X. For deterministic finite automata the problem remains open, due to the asymmetry of the catenation.