RAIRO - Theoretical Informatics and Applications

Research Article

On Shuffle Ideals

Pierre-Cyrille Héam

Laboratoire d'Informatique de Franche-Comté, Université de Franche-Comté, 16 route de Gray, 25030 Besancon Cedex, France; heampc@lifc.univ-fcomte.fr.


A shuffle ideal is a language which is a finite union of languages of the form A*a1 A*...A*ak where A is a finite alphabet and the a i 's are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for this problem. Finally we also present a characterization by subwords of the minimal automaton of a shuffle ideal and study the complexity of basic operations on shuffle ideals.

(Received November 2001)

(Accepted October 2002)

(Online publication February 15 2003)

Mathematics Subject Classification:

  • 68Q45;
  • 68Q70