On the Complexity of Decidable Cases of Commutation Problem for Languages (Extended Abstract)
Wojciech Plandowski, Wojciech Rytter · 2001
We investigate the complexity of basic decidable cases of the commutation problem for languages: testing the equality XY = YX for two languages X, Y , given different types of representations of X, Y. We concentrate on (the most interesting) case when Y is an explicitly given finite language. This is motivated by a renewed interest and recent progress, see (12,1), in an old open problem posed by Conway (2). We show that the complexity of the commutation problem varies from co- NEXPTIME -complete, through P -SP ACE complete and co- NP com- plete, to deterministic polynomial time. Classical types of description are considered: nondeterministic automata with and without cycles, regular expressions and grammars. 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 that of X. For the case of commutation of two finite sets we provide polynomial time algorithms whose time com- plexity beats that of a naive algorithm. For deterministic automata the situation is more complicated since the complexity of concatenation of deterministic automaton language X with a finite set Y is asymmetric: while the minimal dfa's for XY would be polynomial in terms of dfa's for X and Y , that for YX can be exponential.