Affordable Access

On shuffle ideals

Publication Date
  • Computer Science
  • Mathematics


ita0222.dvi Theoretical Informatics and Applications Theoret. Informatics Appl. 36 (2002) 359–384 DOI: 10.1051/ita:2003002 ON SHUFFLE IDEALS ∗ Pierre-Cyrille He´am1 Abstract. A shuffle ideal is a language which is a finite union of lan- guages of the form A�a1A� · · ·A�akA� 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 char- acterization 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. 1. Preliminaries 1.1. Introduction The shu�e product is an operation on languages which is strongly connected to combinatorics on words and which was widely studied in the literature [4, 18, 21, 24, 26]. The main topic of this paper is the algorithmic study of shu�e ideals which are rational languages of the form [A�a1A� � � �A�akA� where A is a �nite alphabet and the ai’s are letters. This is an interesting class of languages which is both connected to combinatorics on words [11, 17] and to the algebraic classi�cation of rational languages: indeed it represents the �rst half level of a hierarchy of star- free languages which was introduced by Straubing [29] and Th�erien [30] and which is still intensively studied [2, 3, 9, 10, 23, 25, 27, 28,31]. � This work was done while the author was at LIAFA, Universite´ Paris 7. 1 Laboratoire d’Informatique de Franche-Comte´, Universite´ de Franche-Comte´, 16 route de Gray, 25030 Besancon Cedex, France; e-mail: c© EDP Sciences 2003 360 P.-C. HE´AM In this paper, we �rst show that a rational language is a shu�e ideal if

There are no comments yet on this publication. Be the first to share your thoughts.