A shuffle ideal is a language which is a finite union of languages of the form where is a finite alphabet and the ’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.
@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},
volume = {36},
year = {2002},
pages = {359-384},
doi = {10.1051/ita:2003002},
mrnumber = {1965422},
zbl = {1034.68056},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 359-384. doi : 10.1051/ita:2003002. http://gdmltest.u-ga.fr/item/ITA_2002__36_4_359_0/
[1] , and, The design and analysis of computer algorithms. Addison-Wesley (1974) 395-400. | MR 413592 | Zbl 0326.68005
[2] , 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] , Opération polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91 (1991) 71-84. | MR 1142558 | Zbl 0751.68031
[4] and, Shuffle factorization is unique, Technical Report. LIAFA, Université Paris 7 (1999). | Zbl 0997.68092
[5] , Transductions and context-free languages. Teubner (1979) Verlag. | MR 549481 | Zbl 0424.68040
[6] , and, On the expressive power of temporal logic for finite words. J. Comput. System Sci. 46 (1993) 271-294. | MR 1228808 | Zbl 0784.03014
[7] , Automata, Languages and Machines, Vol. A. Academic Press (1974). | MR 530382 | Zbl 0317.94045
[8] ,, and, On the temporal analysis of fairness, in 12th ACM Symp. on Principles of Programming Languages (1980) 163-180.
[9] and, 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] , Some complexity results for polynomial rational expressions. Theoret. Comput. Sci. (to appear). | MR 1973175 | Zbl 1042.68063
[11] , Ordering by divisibility in abstract algebras, in Proc. of the London Mathematical Society, Vol. 2 (1952) 326-336. | MR 49867 | Zbl 0047.03402
[12] and, Computing -free nfa from regular expressions in time. RAIRO: Theoret. Informatics Appl. 34 (2000) 257-277. | Numdam | MR 1809860 | Zbl 0971.68091
[13] and, Introduction to automata theory, languages, and computation. Addison-Wesley (1980). | MR 645539 | Zbl 0426.68001
[14] , Tense logic and the theory of linear order, Ph.D. Thesis. University of California, Los Angeles (1968).
[15] , 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] , Representation of events in nerve nets and finite automata. Princeton University Press, Automata Studies (1956) 3-42. | MR 77478
[17] , Combinatorics on words. Cambridge Mathematical Library (1983). | MR 675953 | Zbl 0514.20045
[18] ,,, and, Efficient parallel shuffle recognition. Parallel Process. Lett. 4 (1994) 455-463.
[19] , Computational complexity. Addison Wesley (1994). | MR 1251285 | Zbl 0833.68049
[20] , Automates, réseaux, formules, in Actes des journées “Informatiques et Mathématiques”. Luminy (1984). | Zbl 0631.03026
[21] , and, A constant time string shuffle algorithm on reconfigurable meshes. Int. J. Comput. Math. 68 (1998) 251-259. | MR 1681406 | Zbl 0902.68084
[22] , The temporal logic of programs, in 18th FOCS (1977) 46-57. | MR 502161
[23] and, Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 1-39. | MR 1450862 | Zbl 0872.68119
[24] , 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] , Piecewise testable events, in GI Conf. Springer-Verlag, Lecture Notes in Comput. Sci. 33 (1975) 214-222. | MR 427498 | Zbl 0316.68034
[26] , Le calcul rapide des mélanges de deux mots. Theoret. Comput. Sci. 47 (1986) 181-203. | MR 881211 | Zbl 0638.68081
[27] and, Partially ordered finite monoids and a theorem of I. Simon. J. Algebra 119 (1985) 161-183. | MR 971141 | Zbl 0658.20035
[28] , Characterization of some classes of regular events. Theoret. Comput. Sci. 35 (1985) 17-42. | MR 785905 | Zbl 0604.68066
[29] , Finite semigroups varieties of the form VD. J. Pure Appl. Algebra 36 (1985) 53-94. | MR 782639 | Zbl 0561.20042
[30] , Classification of finite monoids: The language approach. Theoret. Comput. Sci. 14 (1981) 195-208. | MR 614416 | Zbl 0471.20055
[31] , Classifying regular events in symbolic logic. J. Comput. System Sci. 25 360-375. | MR 684265 | Zbl 0503.68055
[32] and, 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] , Classifying discrete temporal properties, in STACS'99. Springer-Verlag, Lecture Notes in Comput. Sci. 1563 (1999) 32-46. | Zbl 0926.03018
[34] , State complexity of regular languages, in Proc. of the International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (1999) 77-88.