On the Shuffle of Star-Free Languages
- Authors: Castiglione, G.; Restivo, A.
- Publication year: 2012
- Type: Articolo in rivista (Articolo in rivista)
- Key words: Regular languages; star-free languages; shuffle of languages; pure submonoids; combinatorics on words.
- OA Link: http://hdl.handle.net/10447/64503
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.