Name
Abstract | ||
|---|---|---|
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 | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.ic.2010.06.002 | Inf. Comput. |
Keywords | Field | DocType |
smaller class,antonio restivo,shuffle product,smallest class,partial result,combinatorial flavor,boolean operation,expressive power,mysterious operation,formal language,increasing interest,process algebra,regular language | Algebraic number,Formal language,Computer science,Arithmetic,Boolean operations in computer-aided design,Regular language,Expressive power,Process calculus | Journal |
Volume | Issue | ISSN |
208 | 11 | Information and Computation |
Citations | PageRank | References |
8 | 0.57 | 7 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| jean berstel | 1 | 664 | 111.00 |
| Luc Boasson | 2 | 490 | 75.99 |
| Olivier Carton | 3 | 381 | 40.97 |
| Jean-Éric Pin | 4 | 112 | 10.57 |
| Antonio Restivo | 5 | 697 | 107.05 |