On the Shuffle of Star-Free Languages
- Autori: Castiglione, G.; Restivo, A.
- Anno di pubblicazione: 2012
- Tipologia: Articolo in rivista (Articolo in rivista)
- Parole Chiave: Regular languages; star-free languages; shuffle of languages; pure submonoids; combinatorics on words.
Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new problems in combinatorics on words.