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.

Berstel, J., Boasson, L., Carton, O., Pin, J., Restivo, A. (2010). The expressive power of the shuffle product. INFORMATION AND COMPUTATION, 208, 1258-1272 [DOI: 10.1016/j.ic.2010.06.002].

The expressive power of the shuffle product

RESTIVO, Antonio
2010-01-01

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.
2010
Berstel, J., Boasson, L., Carton, O., Pin, J., Restivo, A. (2010). The expressive power of the shuffle product. INFORMATION AND COMPUTATION, 208, 1258-1272 [DOI: 10.1016/j.ic.2010.06.002].
File in questo prodotto:
File Dimensione Formato  
Restivo et al. The expressive power of the shuffle product.pdf

Solo gestori archvio

Dimensione 409.7 kB
Formato Adobe PDF
409.7 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/58210
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 13
social impact