On Shuffle Ideals
Laboratoire d'Informatique de Franche-Comté,
Université de Franche-Comté, 16 route de Gray, 25030 Besancon Cedex, France; email@example.com.
Accepted: October 2002
A shuffle ideal is a language which is a finite union of languages of the form A*a1A*...A*ak where A is a finite alphabet and the ai'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.
Mathematics Subject Classification: 68Q45 / 68Q70
© EDP Sciences, 2002