On Shuffle Ideals

Pierre-Cyrille Héam

RAIRO - Theoretical Informatics and Applications (2010)

  • 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*a1A*...A*ak where A is a finite alphabet and the ai'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 36.4 (2010): 359-384. <http://eudml.org/doc/92707>.

@article{Héam2010,
abstract = {
A shuffle ideal is a language which is a finite union of languages of the form A*a1A*...A*ak where A is a finite alphabet and the ai'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},
keywords = {automata; complexity; subwords},
language = {eng},
month = {3},
number = {4},
pages = {359-384},
publisher = {EDP Sciences},
title = {On Shuffle Ideals},
url = {http://eudml.org/doc/92707},
volume = {36},
year = {2010},
}

TY - JOUR
AU - Héam, Pierre-Cyrille
TI - On Shuffle Ideals
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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*a1A*...A*ak where A is a finite alphabet and the ai'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/92707
ER -

References

top
  1. A. Aho, J. Hopcroft and J. Ullman, The design and analysis of computer algorithms. Addison-Wesley (1974) 395-400.  
  2. J. Almeida, Implicit operations on finite 𝒥 -trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra69 (1990) 205-218.  
  3. M. Arfi, Opération polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci.91 (1991) 71-84.  
  4. J. Berstel and L. Boasson, Shuffle factorization is unique, Technical Report. LIAFA, Université Paris 7 (1999).  
  5. J. Berstel, Transductions and context-free languages. Teubner (1979) Verlag.  
  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.  
  7. S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974).  
  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).  
  10. P.-C. Héam, Some complexity results for polynomial rational expressions. Theoret. Comput. Sci. (to appear).  
  11. G. Higman, Ordering by divisibility in abstract algebras, in Proc. of the London Mathematical Society, Vol. 2 (1952) 326-336.  
  12. C. Hagenah and A. Muscholl, Computing ε-free nfa from regular expressions in O(nlog2(n)) time. RAIRO: Theoret. Informatics Appl.34 (2000) 257-277.  
  13. J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley (1980).  
  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.  
  17. M. Lothaire, Combinatorics on words. Cambridge Mathematical Library (1983).  
  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).  
  20. M. Parigot, Automates, réseaux, formules, in Actes des journées ``Informatiques et Mathématiques". Luminy (1984).  
  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.  
  22. A. Pnueli, The temporal logic of programs, in 18th FOCS (1977) 46-57.  
  23. J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems30 (1997) 1-39.  
  24. D.E. Radford, A natural ring basis for shuffle algebra and an application to group schemes. J. Algebra58 (1979) 432-454.  
  25. I. Simon, Piecewise testable events, in GI Conf. Springer-Verlag, Lecture Notes in Comput. Sci. 33 (1975) 214-222.  
  26. J.-C. Spehner, Le calcul rapide des mélanges de deux mots. Theoret. Comput. Sci.47 (1986) 181-203.  
  27. H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon. J. Algebra119 (1985) 161-183.  
  28. J. Stern, Characterization of some classes of regular events. Theoret. Comput. Sci.35 (1985) 17-42.  
  29. H. Straubing, Finite semigroups varieties of the form V*sD. J. Pure Appl. Algebra36 (1985) 53-94.  
  30. D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci.14 (1981) 195-208.  
  31. W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 360-375.  
  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.  
  33. Th. Wilke, Classifying discrete temporal properties, in STACS'99. Springer-Verlag, Lecture Notes in Comput. Sci. 1563 (1999) 32-46.  
  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.