On shuffle ideals
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 4, pp. 359-384.

A shuffle ideal is a language which is a finite union of languages of the form A * a 1 A * A * a k A * 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.

DOI : 10.1051/ita:2003002
Classification : 68Q45, 68Q70
@article{ITA_2002__36_4_359_0,
     author = {H\'eam, Pierre-Cyrille},
     title = {On shuffle ideals},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {359--384},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {4},
     year = {2002},
     doi = {10.1051/ita:2003002},
     mrnumber = {1965422},
     zbl = {1034.68056},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2003002/}
}
TY  - JOUR
AU  - Héam, Pierre-Cyrille
TI  - On shuffle ideals
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2002
SP  - 359
EP  - 384
VL  - 36
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2003002/
DO  - 10.1051/ita:2003002
LA  - en
ID  - ITA_2002__36_4_359_0
ER  - 
%0 Journal Article
%A Héam, Pierre-Cyrille
%T On shuffle ideals
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2002
%P 359-384
%V 36
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2003002/
%R 10.1051/ita:2003002
%G en
%F ITA_2002__36_4_359_0
Héam, Pierre-Cyrille. On shuffle ideals. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 4, pp. 359-384. doi : 10.1051/ita:2003002. http://archive.numdam.org/articles/10.1051/ita:2003002/

[1] A. Aho, J. Hopcroft and J. Ullman, The design and analysis of computer algorithms. Addison-Wesley (1974) 395-400. | MR | Zbl

[2] J. Almeida, Implicit operations on finite 𝒥-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra 69 (1990) 205-218. | MR | Zbl

[3] M. Arfi, Opération polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91 (1991) 71-84. | MR | Zbl

[4] J. Berstel and L. Boasson, Shuffle factorization is unique, Technical Report. LIAFA, Université Paris 7 (1999). | Zbl

[5] J. Berstel, Transductions and context-free languages. Teubner (1979) Verlag. | MR | Zbl

[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. | MR | Zbl

[7] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974). | MR | Zbl

[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). | Zbl

[10] P.-C. Héam, Some complexity results for polynomial rational expressions. Theoret. Comput. Sci. (to appear). | MR | Zbl

[11] G. Higman, Ordering by divisibility in abstract algebras, in Proc. of the London Mathematical Society, Vol. 2 (1952) 326-336. | MR | Zbl

[12] C. Hagenah and A. Muscholl, Computing ϵ-free nfa from regular expressions in O(nlog 2 (n)) time. RAIRO: Theoret. Informatics Appl. 34 (2000) 257-277. | Numdam | MR | Zbl

[13] J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley (1980). | MR | Zbl

[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. | MR

[17] M. Lothaire, Combinatorics on words. Cambridge Mathematical Library (1983). | MR | Zbl

[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). | MR | Zbl

[20] M. Parigot, Automates, réseaux, formules, in Actes des journées “Informatiques et Mathématiques”. Luminy (1984). | Zbl

[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. | MR | Zbl

[22] A. Pnueli, The temporal logic of programs, in 18th FOCS (1977) 46-57. | MR

[23] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 1-39. | MR | Zbl

[24] D.E. Radford, A natural ring basis for shuffle algebra and an application to group schemes. J. Algebra 58 (1979) 432-454. | MR | Zbl

[25] I. Simon, Piecewise testable events, in GI Conf. Springer-Verlag, Lecture Notes in Comput. Sci. 33 (1975) 214-222. | MR | Zbl

[26] J.-C. Spehner, Le calcul rapide des mélanges de deux mots. Theoret. Comput. Sci. 47 (1986) 181-203. | MR | Zbl

[27] H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon. J. Algebra 119 (1985) 161-183. | MR | Zbl

[28] J. Stern, Characterization of some classes of regular events. Theoret. Comput. Sci. 35 (1985) 17-42. | MR | Zbl

[29] H. Straubing, Finite semigroups varieties of the form V*D. J. Pure Appl. Algebra 36 (1985) 53-94. | MR | Zbl

[30] D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. | MR | Zbl

[31] W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 360-375. | MR | Zbl

[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. | MR | Zbl

[33] Th. Wilke, Classifying discrete temporal properties, in STACS'99. Springer-Verlag, Lecture Notes in Comput. Sci. 1563 (1999) 32-46. | Zbl

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

Cité par Sources :