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}^{*}\cdots {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 : https://doi.org/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},
zbl = {1034.68056},
mrnumber = {1965422},
language = {en},
url = {http://www.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
DA  - 2002///
SP  - 359
EP  - 384
VL  - 36
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2003002/
UR  - https://zbmath.org/?q=an%3A1034.68056
UR  - https://www.ams.org/mathscinet-getitem?mr=1965422
UR  - https://doi.org/10.1051/ita:2003002
DO  - 10.1051/ita:2003002
LA  - en
ID  - ITA_2002__36_4_359_0
ER  - 
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://www.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 413592 | Zbl 0326.68005

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

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

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

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

[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 1228808 | Zbl 0784.03014

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

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

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

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

[12] C. Hagenah and A. Muscholl, Computing $ϵ$-free nfa from regular expressions in $O\left(n{log}^{2}\left(n\right)\right)$ time. RAIRO: Theoret. Informatics Appl. 34 (2000) 257-277. | Numdam | MR 1809860 | Zbl 0971.68091

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

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

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

[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 1251285 | Zbl 0833.68049

[20] M. Parigot, Automates, réseaux, formules, in Actes des journées “Informatiques et Mathématiques”. Luminy (1984). | Zbl 0631.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. | MR 1681406 | Zbl 0902.68084

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

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

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

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

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

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

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

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

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

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

[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 1450623 | Zbl 1001.03018

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

Cité par Sources :