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.

Castiglione, G., & Restivo, A. (2012). On the Shuffle of Star-Free Languages. FUNDAMENTA INFORMATICAE, 116, 35-44 [10.3233/FI-2012-666].

On the Shuffle of Star-Free Languages

CASTIGLIONE, Giuseppa;RESTIVO, Antonio
2012

Abstract

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.
Settore INF/01 - Informatica
Castiglione, G., & Restivo, A. (2012). On the Shuffle of Star-Free Languages. FUNDAMENTA INFORMATICAE, 116, 35-44 [10.3233/FI-2012-666].
File in questo prodotto:
File Dimensione Formato  
[22]ShuffleFI.pdf

Solo gestori archvio

Dimensione 1.59 MB
Formato Adobe PDF
1.59 MB 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: http://hdl.handle.net/10447/64503
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact