On Shuffle Closures of Commutative Regular Languages

摘要

In this paper, we present two characterizations of those commutative regular languages whose shuffle closures are regular as well. In particular, from our characterizations it follows that it is decidable whether the shuffle closure of a commutative regular language is regular.