EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO-Theor. Inf. Appl.
Volume 36, Number 4, October-December 2002
Page(s) 359 - 384
DOI 10.1051/ita:2003002

Theoret. Informatics Appl. 36, 359-384 (2002)
DOI: 10.1051/ita:2003002

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.


(Received November, 2001. Accepted October, 2002)

Abstract

A shuffle ideal is a language which is a finite union of languages of the form $A^*a_1A^*\cdots A^*a_kA^*$ 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


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.