6533b7d7fe1ef96bd1268f2c
RESEARCH PRODUCT
On the Shuffle of Star-Free Languages
Antonio RestivoGiusi Castiglionesubject
Discrete mathematicsAlgebra and Number TheorySettore INF/01 - Informaticapure submonoidGeneral problemAbstract family of languagesRegular languageComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Star (graph theory)star-free languageCone (formal languages)shuffle of languagePumping lemma for regular languagesTheoretical Computer ScienceCombinatorics on wordsComputational Theory and MathematicsRegular languagecombinatorics on words.Information SystemsMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2012-01-01 | Fundamenta Informaticae |