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.  Zbl0326.68005
  2. J. Almeida, Implicit operations on finite 𝒥 -trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra69 (1990) 205-218.  Zbl0724.08003
  3. M. Arfi, Opération polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci.91 (1991) 71-84.  Zbl0751.68031
  4. J. Berstel and L. Boasson, Shuffle factorization is unique, Technical Report. LIAFA, Université Paris 7 (1999).  Zbl0997.68092
  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.  Zbl0784.03014
  7. S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press (1974).  Zbl0317.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).  
  10. P.-C. Héam, Some complexity results for polynomial rational expressions. Theoret. Comput. Sci. (to appear).  Zbl1042.68063
  11. G. Higman, Ordering by divisibility in abstract algebras, in Proc. of the London Mathematical Society, Vol. 2 (1952) 326-336.  Zbl0047.03402
  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.  Zbl0971.68091
  13. J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley (1980).  Zbl0847.68065
  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).  Zbl0514.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).  Zbl0833.68049
  20. M. Parigot, Automates, réseaux, formules, in Actes des journées ``Informatiques et Mathématiques". Luminy (1984).  Zbl0631.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.  Zbl0902.68084
  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.  Zbl0872.68119
  24. D.E. Radford, A natural ring basis for shuffle algebra and an application to group schemes. J. Algebra58 (1979) 432-454.  Zbl0409.16011
  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.  Zbl0638.68081
  27. H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon. J. Algebra119 (1985) 161-183.  Zbl0658.20035
  28. J. Stern, Characterization of some classes of regular events. Theoret. Comput. Sci.35 (1985) 17-42.  Zbl0604.68066
  29. H. Straubing, Finite semigroups varieties of the form V*sD. J. Pure Appl. Algebra36 (1985) 53-94.  Zbl0561.20042
  30. D. Thérien, Classification of finite monoids: The language approach. Theoret. Comput. Sci.14 (1981) 195-208.  Zbl0471.20055
  31. W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 360-375.  Zbl0503.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.  
  33. Th. Wilke, Classifying discrete temporal properties, in STACS'99. Springer-Verlag, Lecture Notes in Comput. Sci. 1563 (1999) 32-46.  Zbl0926.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.  

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.