Commutative one-counter languages are regular (Q800097): Difference between revisions

Let X be a finite alphabet. A language \(L\subseteq X^*\) is said to be commutative if \(L=c(L)\), where c(L) is the union of the commutative closures c(w), for all w in L. The commutative closure of \(w\in X^*\) is defined as the set of all words obtained from w by permuting occurrences of symbols in w. The family of one-counter languages is said to be the smallest family of languages that contains the semi-Dyck language over one pair of parantheses and is closed under morphisms, inverse morphisms and intersection with regular sets. By means of a new characterization of commutative regular languages the authors prove that every commutative one-counter language is regular.