# On shuffle ideals

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2002)

- 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 - Informatique Théorique et Applications 36.4 (2002): 359-384. <http://eudml.org/doc/245355>.

@article{Héam2002,

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 $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.},

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

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {automata; complexity; subwords},

language = {eng},

number = {4},

pages = {359-384},

publisher = {EDP-Sciences},

title = {On shuffle ideals},

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

volume = {36},

year = {2002},

}

TY - JOUR

AU - Héam, Pierre-Cyrille

TI - On shuffle ideals

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2002

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^*a_1A^*\cdots A^*a_kA^*$ 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.

LA - eng

KW - automata; complexity; subwords

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

ER -

## References

top- [1] A. Aho, J. Hopcroft and J. Ullman, The design and analysis of computer algorithms. Addison-Wesley (1974) 395-400. Zbl0326.68005MR413592
- [2] J. Almeida, Implicit operations on finite $\mathcal{J}$-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra 69 (1990) 205-218. Zbl0724.08003MR1090741
- [3] M. Arfi, Opération polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91 (1991) 71-84. Zbl0751.68031MR1142558
- [4] J. Berstel and L. Boasson, Shuffle factorization is unique, Technical Report. LIAFA, Université Paris 7 (1999). Zbl0997.68092
- [5] J. Berstel, Transductions and context-free languages. Teubner (1979) Verlag. Zbl0424.68040MR549481
- [6] 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.03014MR1228808
- [7] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974). Zbl0317.94045MR530382
- [8] 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.
- [9] 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). Zbl1073.68046
- [10] P.-C. Héam, Some complexity results for polynomial rational expressions. Theoret. Comput. Sci. (to appear). Zbl1042.68063MR1973175
- [11] G. Higman, Ordering by divisibility in abstract algebras, in Proc. of the London Mathematical Society, Vol. 2 (1952) 326-336. Zbl0047.03402MR49867
- [12] C. Hagenah and A. Muscholl, Computing $\u03f5$-free nfa from regular expressions in $O\left(n{log}^{2}\left(n\right)\right)$ time. RAIRO: Theoret. Informatics Appl. 34 (2000) 257-277. Zbl0971.68091MR1809860
- [13] J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley (1980). Zbl0426.68001MR645539
- [14] J.A. Kamp, Tense logic and the theory of linear order, Ph.D. Thesis. University of California, Los Angeles (1968).
- [15] 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).
- [16] S.C. Kleene, Representation of events in nerve nets and finite automata. Princeton University Press, Automata Studies (1956) 3-42. MR77478
- [17] M. Lothaire, Combinatorics on words. Cambridge Mathematical Library (1983). Zbl0514.20045MR675953
- [18] 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.
- [19] C.H. Papadimitriou, Computational complexity. Addison Wesley (1994). Zbl0833.68049MR1251285
- [20] M. Parigot, Automates, réseaux, formules, in Actes des journées “Informatiques et Mathématiques”. Luminy (1984). Zbl0631.03026
- [21] 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.68084MR1681406
- [22] A. Pnueli, The temporal logic of programs, in 18th FOCS (1977) 46-57. MR502161
- [23] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 1-39. Zbl0872.68119MR1450862
- [24] D.E. Radford, A natural ring basis for shuffle algebra and an application to group schemes. J. Algebra 58 (1979) 432-454. Zbl0409.16011MR540649
- [25] I. Simon, Piecewise testable events, in GI Conf. Springer-Verlag, Lecture Notes in Comput. Sci. 33 (1975) 214-222. Zbl0316.68034MR427498
- [26] J.-C. Spehner, Le calcul rapide des mélanges de deux mots. Theoret. Comput. Sci. 47 (1986) 181-203. Zbl0638.68081MR881211
- [27] H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon. J. Algebra 119 (1985) 161-183. Zbl0658.20035MR971141
- [28] J. Stern, Characterization of some classes of regular events. Theoret. Comput. Sci. 35 (1985) 17-42. Zbl0604.68066MR785905
- [29] H. Straubing, Finite semigroups varieties of the form V$*$D. J. Pure Appl. Algebra 36 (1985) 53-94. Zbl0561.20042MR782639
- [30] D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. Zbl0471.20055MR614416
- [31] W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 360-375. Zbl0503.68055MR684265
- [32] 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. Zbl1001.03018MR1450623
- [33] Th. Wilke, Classifying discrete temporal properties, in STACS’99. Springer-Verlag, Lecture Notes in Comput. Sci. 1563 (1999) 32-46. Zbl0926.03018
- [34] 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.