Combinatorics of Unique Maximal Factorization Families (UMFFs)

• Autorzy: Daykin D.E. , Daykin J.W. , Smyth W.F. (Bill)
• 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

EN

alphabet; circ-UMFF; concatenate; dictionary; factor; lexicographic order; Lyndon; maximal; string; total order; UMFF; word

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 97, nr 3
• Strony: 295--309
• Opis fizyczny: . Bibliogr. 16 poz.

Twórcy

autor

Daykin D.E.

autor

Daykin J.W.

autor

Smyth W.F. (Bill)

• Department of Computer Science, Royal Holloway College, University of London, Egham, TW20 0EX, UK,

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