On shuffle ideals

Héam, Pierre-Cyrille

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.

Classification : 68Q45, 68Q70

[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\left(n{log}^2\left(n\right)\right)$ 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.