Yuval Filmus (with help from Mark Reitblatt) shows algorithms and hardness results for [deciding "circular languages"][1]. 


  [1]: http://cstheory.stackexchange.com/questions/4254/a-special-class-of-regular-languages-circular-languages-is-it-known