Laboratoire d'Informatique de Franche-Comté, Université de Franche-Comté, 16 route de Gray, 25030 Besancon Cedex, France; firstname.lastname@example.org.
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: