6533b7d6fe1ef96bd1267182
RESEARCH PRODUCT
The expressive power of the shuffle product
Antonio RestivoLuc BoassonJean BerstelJean-eric PinOlivier Cartonsubject
Class (set theory)Computer science[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technologyStar (graph theory)01 natural sciencesExpressive powerTheoretical Computer ScienceRegular languageFormal language0202 electrical engineering electronic engineering information engineeringArithmeticAlgebraic numberComputingMilieux_MISCELLANEOUSDiscrete mathematicsComputer Science Applicationsshuffle operatorComputational Theory and Mathematics010201 computation theory & mathematicsProduct (mathematics)Formal language020201 artificial intelligence & image processingBoolean operations in computer-aided designWord (computer architecture)Information Systemsdescription
International audience; There is an increasing interest in the shuffle product on formal languages, mainly because it is a standard tool for modeling process algebras. It still remains a mysterious operation on regular languages.Antonio Restivo proposed as a challenge to characterize the smallest class of languages containing the singletons and closed under Boolean operations, product and shuffle. This problem is still widely open, but we present some partial results on it. We also study some other smaller classes, including the smallest class containing the languages composed of a single word of length 2 which is closed under Boolean operations and shuffle by a letter (resp. shuffle by a letter and by the star of a letter). The proof techniques have both an algebraic and a combinatorial flavor.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-11-01 |