On shuffle ideals

Pierre-Cyrille Héam

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

  • Volume: 36, Issue: 4, page 359-384
  • ISSN: 0988-3754

Abstract

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

How to cite

top

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

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.