PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Combinatorics of Unique Maximal Factorization Families (UMFFs)

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Suppose a set W of strings contains exactly one rotation (cyclic shift) of every primitive string on some alphabet Σ. Then W is a circ-UMFF if and only if every word in Σ+ has a unique maximal factorization over W. The classic circ-UMFF is the set of Lyndon words based on lexicographic ordering (1958). Duval (1983) designed a linear sequential Lyndon factorization algorithm; a corresponding PRAMparallel algorithmwas described by J. Daykin, Iliopoulos and Smyth (1994). Daykin and Daykin defined new circ-UMFFs based on various methods for totally ordering sets of strings (2003), and further described the structure of all circ-UMFFs (2008). Here we prove new combinatorial results for circ-UMFFs, and in particular for the case of Lyndon words. We introduce Acrobat and Flight Deck circ-UMFFs, and describe some of our results in terms of dictionaries. Applications of circ-UMFFs pertain to structured methods for concatenating and factoring strings over ordered alphabets, and those of Lyndon words are wide ranging and multidisciplinary.
Słowa kluczowe
Wydawca
Rocznik
Strony
295--309
Opis fizyczny
. Bibliogr. 16 poz.
Twórcy
autor
autor
Bibliografia
  • [1] S. Brlek and G. Melanc¸on and G. Paquin, Properties of the extremal infinite smooth words, Discrete Math. Theor. Comput. Sci. 9 : 2 (2007) 33-50.
  • [2] M. Chemillier, Periodic musical sequences and Lyndon words, Soft Computing - A Fusion of Foundations, Methodologies and Applications, Springer-Verlag, ISSN 1432-7643 (Print) 1433-7479 (Online), Vol. 8, Issue 9 (September 2004) 611-616.
  • [3] M. Crochemore, J. D´esarm´enien and D. Perrin, A note on the Burrows-Wheeler transformation, Theoret. Comput. Sci. 332 (1-3) (2005) 567-572.
  • [4] K.T. Chen, R.H. Fox and R.C. Lyndon, Free differential calculus, IV - The quotient groups of the lower central series, Ann. Math. 68 (1958) 81-95.
  • [5] D.E. Daykin, A 2n algorithm factors an n-string into Lyndon words, to appear in J. Discrete Algorithms. D.E. Daykin et al. /Combinatorics of Unique Maximal Factorization Families (UMFFs) 309
  • [6] D.E. Daykin and J.W. Daykin, Lyndon-like and V-order factorizations of strings, J. Discrete Algorithms 1 (2003) 357-365.
  • [7] D.E. Daykin and J.W. Daykin, Properties and construction of unique maximal factorization families for strings, Internat. J. Found. Comput. Sci. Vol. 19, No. 4 (2008) 1073-1084.
  • [8] J.W. Daykin, C.S. Iliopoulos and W.F. Smyth, Parallel RAM algorithms for factorizing words, Theoret. Comput. Sci. 127 (1) (1994) 53-67.
  • [9] J.P. Duval, Factorizing words over an ordered alphabet, J. Algorithms 4 (1983) 363-381.
  • [10] C.S. Iliopoulos, D. Moore and W.F. Smyth, The covers of a circular Fibonacci string, J. Combin. Math. Combin. Comput. 26 (1998) 227-236.
  • [11] C.S. Iliopoulos and W.F. Smyth, Optimal algorithms for computing the canonical form of a circular string, Theoret. Comput. Sci. 92 (1) (1992) 87-105.
  • [12] D.L. Kreher and D.R. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press (1998).
  • [13] M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983; 2nd Edition, Cambridge University Press, Cambridge, 1997.
  • [14] A. de Luca, A division property of the FibonacciWord, Information Processing Letters 54 (6) (1995) 307-312.
  • [15] L. Perret, A chosen ciphertext attack on a public key cryptosystem based on Lyndon words, Proceedings of International Workshop on Coding and Cryptography (WCC 2005), (January 2005) 235-244.
  • [16] Bill Smyth, Computing patterns in strings, Pearson (2003).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0008-0073
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.