# On Shuffle Ideals

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 36, Issue: 4, page 359-384
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHéam, Pierre-Cyrille. "On Shuffle Ideals." RAIRO - Theoretical Informatics and Applications 36.4 (2010): 359-384. <http://eudml.org/doc/92707>.

@article{Héam2010,

abstract = {
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.
},

author = {Héam, Pierre-Cyrille},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {automata; complexity; subwords},

language = {eng},

month = {3},

number = {4},

pages = {359-384},

publisher = {EDP Sciences},

title = {On Shuffle Ideals},

url = {http://eudml.org/doc/92707},

volume = {36},

year = {2010},

}

TY - JOUR

AU - Héam, Pierre-Cyrille

TI - On Shuffle Ideals

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 36

IS - 4

SP - 359

EP - 384

AB -
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.

LA - eng

KW - automata; complexity; subwords

UR - http://eudml.org/doc/92707

ER -

## References

top- A. Aho, J. Hopcroft and J. Ullman, The design and analysis of computer algorithms. Addison-Wesley (1974) 395-400. Zbl0326.68005
- J. Almeida, Implicit operations on finite $\mathcal{J}$-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra69 (1990) 205-218. Zbl0724.08003
- M. Arfi, Opération polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci.91 (1991) 71-84. Zbl0751.68031
- J. Berstel and L. Boasson, Shuffle factorization is unique, Technical Report. LIAFA, Université Paris 7 (1999). Zbl0997.68092
- J. Berstel, Transductions and context-free languages. Teubner (1979) Verlag. Zbl0424.68040
- J. Cohen, D. Perrin and J.-E. Pin, On the expressive power of temporal logic for finite words. J. Comput. System Sci.46 (1993) 271-294. Zbl0784.03014
- S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974). Zbl0317.94045
- D. Gabbay, A. Pnueli, S. Shelah and J. Stavi, On the temporal analysis of fairness, in 12th ACM Symp. on Principles of Programming Languages (1980) 163-180.
- C. Glasser and H. Schmidt, Level 5/2 of the straubing-thérien hierarchy for two-letter alphabets, in Conference on Developments in Language Theory (DLT). Vienna (2001).
- P.-C. Héam, Some complexity results for polynomial rational expressions. Theoret. Comput. Sci. (to appear).
- G. Higman, Ordering by divisibility in abstract algebras, in Proc. of the London Mathematical Society, Vol. 2 (1952) 326-336. Zbl0047.03402
- C. Hagenah and A. Muscholl, Computing ε-free nfa from regular expressions in O(nlog2(n)) time. RAIRO: Theoret. Informatics Appl.34 (2000) 257-277. Zbl0971.68091
- J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley (1980). Zbl0426.68001
- J.A. Kamp, Tense logic and the theory of linear order, Ph.D. Thesis. University of California, Los Angeles (1968).
- O. Katai, Completeness and the expressive power of next time temporal logical system by semantic tableau method, Technical Report RR-0109. Inria, Institut National de Recherche en Informatique et en Automatique (1981).
- S.C. Kleene, Representation of events in nerve nets and finite automata. Princeton University Press, Automata Studies (1956) 3-42.
- M. Lothaire, Combinatorics on words. Cambridge Mathematical Library (1983). Zbl0514.20045
- M. Nivat, G.D.S. Ramkumar, C. Pandu Rangan, A. Saoudi and R. Sundaram, Efficient parallel shuffle recognition. Parallel Process. Lett.4 (1994) 455-463.
- C.H. Papadimitriou, Computational complexity. Addison Wesley (1994). Zbl0833.68049
- M. Parigot, Automates, réseaux, formules, in Actes des journées ``Informatiques et Mathématiques". Luminy (1984). Zbl0631.03026
- B. Pradeep, C. Murthy and S. Ram, A constant time string shuffle algorithm on reconfigurable meshes. Int. J. Comput. Math.68 (1998) 251-259. Zbl0902.68084
- A. Pnueli, The temporal logic of programs, in 18th FOCS (1977) 46-57.
- J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems30 (1997) 1-39. Zbl0872.68119
- D.E. Radford, A natural ring basis for shuffle algebra and an application to group schemes. J. Algebra58 (1979) 432-454. Zbl0409.16011
- I. Simon, Piecewise testable events, in GI Conf. Springer-Verlag, Lecture Notes in Comput. Sci. 33 (1975) 214-222.
- J.-C. Spehner, Le calcul rapide des mélanges de deux mots. Theoret. Comput. Sci.47 (1986) 181-203. Zbl0638.68081
- H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon. J. Algebra119 (1985) 161-183.
- J. Stern, Characterization of some classes of regular events. Theoret. Comput. Sci.35 (1985) 17-42. Zbl0604.68066
- H. Straubing, Finite semigroups varieties of the form V*sD. J. Pure Appl. Algebra36 (1985) 53-94. Zbl0561.20042
- D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci.14 (1981) 195-208.
- W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 360-375. Zbl0503.68055
- D. Thérien and Th. Wilke, Temporal logic and semidirect products: An effective characterization of the until hierarchy, in Proc. of the 37th Annual Symposium on Foundations of Computer Science. IEEE (1996) 256-263.
- Th. Wilke, Classifying discrete temporal properties, in STACS'99. Springer-Verlag, Lecture Notes in Comput. Sci. 1563 (1999) 32-46. Zbl0926.03018
- S. Yu, State complexity of regular languages, in Proc. of the International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (1999) 77-88.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.