Words over an ordered alphabet and suffix permutations
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 249-259.

Given an ordered alphabet and a permutation, according to the lexicographic order, on the set of suffixes of a word w, we present in this article a linear time and space method to determine whether a word w' has the same permutation on its suffixes. Using this method, we are then also able to build the class of all the words having the same permutation on their suffixes, first of all the smallest one. Finally, we note that this work can lead to a method for generating a Lyndon word randomly in linear time or for computing the set of Lyndon words of length n.

DOI : 10.1051/ita:2002012
Classification : 68R15
Mots-clés : suffix permutation, Lyndon words 
@article{ITA_2002__36_3_249_0,
     author = {Duval, Jean-Pierre and Lefebvre, Arnaud},
     title = {Words over an ordered alphabet and suffix permutations},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {249--259},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {3},
     year = {2002},
     doi = {10.1051/ita:2002012},
     mrnumber = {1958242},
     zbl = {1013.68153},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita:2002012/}
}
TY  - JOUR
AU  - Duval, Jean-Pierre
AU  - Lefebvre, Arnaud
TI  - Words over an ordered alphabet and suffix permutations
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2002
SP  - 249
EP  - 259
VL  - 36
IS  - 3
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita:2002012/
DO  - 10.1051/ita:2002012
LA  - en
ID  - ITA_2002__36_3_249_0
ER  - 
%0 Journal Article
%A Duval, Jean-Pierre
%A Lefebvre, Arnaud
%T Words over an ordered alphabet and suffix permutations
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2002
%P 249-259
%V 36
%N 3
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita:2002012/
%R 10.1051/ita:2002012
%G en
%F ITA_2002__36_3_249_0
Duval, Jean-Pierre; Lefebvre, Arnaud. Words over an ordered alphabet and suffix permutations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 249-259. doi : 10.1051/ita:2002012. https://www.numdam.org/articles/10.1051/ita:2002012/

[1] M. Crochemore, C. Hancart and T. Lecroq, Algorithmique du texte. Vuibert (2001). | Zbl

[2] J.-P. Duval, Factorizing Words over an Ordered Alphabet. J. Algorithms 4 (1983) 363-381. | MR | Zbl

[3] E.M. Mccreight, A Space-Economical Suffix Tree Construction Algorithm. J. Algorithms 23 (1976) 262-272. | MR | Zbl

[4] C. Hohlweg and C. Reutenauer, Lyndon words, permutations and trees, Rapport interne 2002-017. Université Louis Pasteur de Strasbourg. | MR | Zbl

  • Amir, Amihood; Kondratovsky, Eitan; Marcus, Shoshana; Sokol, Dina Linear Time Reconstruction of Parameterized Strings from Parameterized Suffix and LCP Arrays for Constant-Sized Alphabets, String Processing and Information Retrieval, Volume 14899 (2025), p. 1 | DOI:10.1007/978-3-031-72200-4_1
  • Amir, Amihood; Kondratovsky, Eitan; Landau, Gad M.; Marcus, Shoshana; Sokol, Dina Reconstructing parameterized strings from parameterized suffix and LCP arrays, Theoretical Computer Science, Volume 981 (2024), p. 114230 | DOI:10.1016/j.tcs.2023.114230
  • Kumagai, Koshiro; Hendrian, Diptarama; Yoshinaka, Ryo; Shinohara, Ayumi Inferring Strings from Position Heaps in Linear Time, WALCOM: Algorithms and Computation, Volume 13973 (2023), p. 115 | DOI:10.1007/978-3-031-27051-2_11
  • Amir, Amihood; Guerra, Concettina; Kondratovsky, Eitan; Landau, Gad M.; Marcus, Shoshana; Sokol, Dina Reconstructing Parameterized Strings from Parameterized Suffix and LCP Arrays, String Processing and Information Retrieval, Volume 13617 (2022), p. 55 | DOI:10.1007/978-3-031-20643-6_5
  • Gelle, Kitti; Iván, Szabolcs Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info, International Journal of Foundations of Computer Science, Volume 30 (2019) no. 06n07, p. 1029 | DOI:10.1142/s0129054119400276
  • Gelle, Kitti; Iván, Szabolcs Recognizing Union-Find trees is NP-complete, Information Processing Letters, Volume 131 (2018), p. 7 | DOI:10.1016/j.ipl.2017.11.003
  • Gelle, Kitti; Iván, Szabolcs Recognizing Union-Find Trees Built Up Using Union-By-Rank Strategy is NP-Complete, Descriptional Complexity of Formal Systems, Volume 10316 (2017), p. 152 | DOI:10.1007/978-3-319-60252-3_12
  • Nakashima, Yuto; Okabe, Takashi; I, Tomohiro; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki Inferring strings from Lyndon factorization, Theoretical Computer Science, Volume 689 (2017), p. 147 | DOI:10.1016/j.tcs.2017.05.038
  • Starikovskaya, Tatiana; Vildhøj, Hjalte Wedel A Suffix Tree Or Not a Suffix Tree?, Combinatorial Algorithms, Volume 8986 (2015), p. 338 | DOI:10.1007/978-3-319-19315-1_30
  • Starikovskaya, Tatiana; Vildhøj, Hjalte Wedel A suffix tree or not a suffix tree?, Journal of Discrete Algorithms, Volume 32 (2015), p. 14 | DOI:10.1016/j.jda.2015.01.005
  • I, Tomohiro; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki Inferring strings from suffix trees and links on a binary alphabet, Discrete Applied Mathematics, Volume 163 (2014), p. 316 | DOI:10.1016/j.dam.2013.02.033
  • Mantaci, Sabrina; Restivo, Antonio; Rosone, Giovanna; Sciortino, Marinella Suffix array and Lyndon factorization of a text, Journal of Discrete Algorithms, Volume 28 (2014), p. 2 | DOI:10.1016/j.jda.2014.06.001
  • Nakashima, Yuto; Okabe, Takashi; I, Tomohiro; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki Inferring Strings from Lyndon Factorization, Mathematical Foundations of Computer Science 2014, Volume 8635 (2014), p. 565 | DOI:10.1007/978-3-662-44465-8_48
  • Bonomo, Silvia; Mantaci, Sabrina; Restivo, Antonio; Rosone, Giovanna; Sciortino, Marinella Suffixes, Conjugates and Lyndon Words, Developments in Language Theory, Volume 7907 (2013), p. 131 | DOI:10.1007/978-3-642-38771-5_13
  • Likhomanov, Konstantin M.; Shur, Arseny M. Two Combinatorial Criteria for BWT Images, Computer Science – Theory and Applications, Volume 6651 (2011), p. 385 | DOI:10.1007/978-3-642-20712-9_30
  • Grossi, Roberto A quick tour on suffix arrays and compressed suffix arrays, Theoretical Computer Science, Volume 412 (2011) no. 27, p. 2964 | DOI:10.1016/j.tcs.2010.12.036
  • I, Tomohiro; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki Verifying and enumerating parameterized border arrays, Theoretical Computer Science, Volume 412 (2011) no. 50, p. 6959 | DOI:10.1016/j.tcs.2011.09.008
  • I., Tomohiro; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki Verifying a Parameterized Border Array in O(n 1.5) Time, Combinatorial Pattern Matching, Volume 6129 (2010), p. 238 | DOI:10.1007/978-3-642-13509-5_22
  • I, Tomohiro; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki Counting and Verifying Maximal Palindromes, String Processing and Information Retrieval, Volume 6393 (2010), p. 135 | DOI:10.1007/978-3-642-16321-0_13
  • I, Tomohiro; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki Counting Parameterized Border Arrays for a Binary Alphabet, Language and Automata Theory and Applications, Volume 5457 (2009), p. 422 | DOI:10.1007/978-3-642-00982-2_36
  • Brlek, S.; Lachaud, J.-O.; Provençal, X.; Reutenauer, C. Lyndon Christoffel digitally convex, Pattern Recognition, Volume 42 (2009) no. 10, p. 2239 | DOI:10.1016/j.patcog.2008.11.010
  • Schürmann, Klaus-Bernd; Stoye, Jens Counting suffix arrays and strings, Theoretical Computer Science, Volume 395 (2008) no. 2-3, p. 220 | DOI:10.1016/j.tcs.2008.01.011
  • Schürmann, Klaus-Bernd; Stoye, Jens Counting Suffix Arrays and Strings, String Processing and Information Retrieval, Volume 3772 (2005), p. 55 | DOI:10.1007/11575832_8
  • Crochemore, Maxime; Désarménien, Jacques; Perrin, Dominique A note on the Burrows–Wheeler transformation, Theoretical Computer Science, Volume 332 (2005) no. 1-3, p. 567 | DOI:10.1016/j.tcs.2004.11.014

Cité par 24 documents. Sources : Crossref