×
Daykin, David E.; Daykin, Jacqueline W.; Smyth, W. F.

A linear partitioning algorithm for hybrid Lyndons using \(V\)-order. (English) Zbl 1292.68130

Theor. Comput. Sci. 483, 149-161 (2013).
Summary: In this paper we extend previous work on unique maximal factorization families (UMFFs) and a total (but non-lexicographic) ordering of strings called \(V\)-order. We present new combinatorial results for \(V\)-order, in particular concatenation under \(V\)-order. We propose linear-time RAM algorithms for string comparison in \(V\)-order and for Lyndon-like factorization of a string into \(V\)-words. This asymptotic efficiency thus matches that of the corresponding algorithms for lexicographical order. Finally, we introduce hybrid Lyndon words as a generalization of standard Lyndon words, and hence propose extensions of factorization algorithms to other forms of order.

Cited in 1 Review
Cited in 8 Documents

MSC:

68R15 Combinatorics on words
68W32 Algorithms on strings

Keywords:

alphabet; circ-UMFF; lexicographic order; total order; unique maximal factorization family (UMFF); \(V\)-order; \(V\)-word; partitioning algorithm; concatenation; linear-time RAM algorithms; string comparison; hybrid Lyndon words; factorization algorithms

Software:

STAR
Cite Review PDF
Full Text: DOI

References:

[1] Chemillier, M., Periodic musical sequences and Lyndon words, Soft Comput., 8-9, 611-616 (2004), ISSN 1432-7643 (Print) 1433-7479 (Online) · Zbl 1064.00506
[2] Chemillier, M.; Truchet, C., Computation of words satisfying the rhythmic oddity property (after Simha Arom’s works), Inform. Process. Lett., 86, 255-261 (2003) · Zbl 1162.68509
[3] Crochemore, M.; Désarménien, J.; Perrin, D., A note on the Burrows-Wheeler transformation, Theoret. Comput. Sci., 332, 1-3, 567-572 (2005) · Zbl 1070.68126
[4] Chen, K. T.; Fox, R. H.; Lyndon, R. C., Free differential calculus IV—the quotient groups of the lower central series, Ann. Math., 68, 81-95 (1958) · Zbl 0083.01403
[5] Cummings, L. J.; Mayes, M. E., Shuffled Lyndon words, ARS Combin., 33, 47-56 (1992) · Zbl 0849.05005
[6] Daykin, D. E., Ordered ranked posets, representations of integers and inequalities from extremal poset problems, (Rival, I., Graphs and Order. Graphs and Order, Proceedings of a Conference in Banff, Canada (1984), NATO Advanced Sciences Institutes Series C: Mathematical and Physical Sciences, vol. 147 (1985), Reidel: Reidel Dordrecht-Boston), 395-412 · Zbl 0573.06003
[7] Daykin, D. E., Algorithms for the Lyndon unique maximal factorization, J. Combin. Math. Combin. Comput., 77, 65-74 (2011) · Zbl 1233.05190
[8] Danh, T.-N.; Daykin, D. E., The structure of \(V\)-order for integer vectors, (Hilton, A. J.W., Congressus Numerantium, vol. 113 (1996), Utilitas Mat. Pub. Inc.: Utilitas Mat. Pub. Inc. Winnipeg, Canada), 43-53 · Zbl 0898.15003
[9] Daykin, D. E.; Daykin, J. W., Lyndon-like and \(V\)-order factorizations of strings, J. Discrete Algorithms, 1, 357-365 (2003) · Zbl 1100.68087
[10] Daykin, D. E.; Daykin, J. W., Properties and construction of unique maximal factorization families for strings, Internat. J. Found. Comput. Sci., 19-4, 1073-1084 (2008) · Zbl 1155.68063
[12] Daykin, D. E.; Daykin, J. W.; Smyth, W. F.; Janicki, R.; Puglisi, S. J.; Rahman, M. S., Combinatorics of Unique Maximal Factorization Families (UMFFs), Special String Masters Issue. Special String Masters Issue, Fund. Inform., 97, 3, 295-309 (2009) · Zbl 1211.68297
[13] Daykin, D. E.; Daykin, J. W.; Smyth, W. F., String comparison and Lyndon-like factorization using \(V\)-order in linear time, (Giancarlo, R.; Manzini, G., Proc. 22nd Annual Symposium on Combinatorial Pattern Matching. Proc. 22nd Annual Symposium on Combinatorial Pattern Matching, LNCS, vol. 6661 (2011)), 65-76 · Zbl 1339.68329
[14] Daykin, J. W.; Iliopoulos, C. S.; Smyth, W. F., Parallel RAM algorithms for factorizing words, Theoret. Comput. Sci., 127, 1, 53-67 (1994) · Zbl 0805.68057
[15] Delgrange, O.; Rivals, E., STAR: an algorithm to search for tandem approximate repeats, Bioinformatics, 20-16, 2812-2820 (2004)
[16] Duval, J. P., Factorizing words over an ordered alphabet, J. Algorithms, 4, 363-381 (1983) · Zbl 0532.68061
[18] Iliopoulos, C. S.; Smyth, W. F., Optimal algorithms for computing the canonical form of a circular string, Theoret. Comput. Sci., 92, 1, 87-105 (1992) · Zbl 0747.68029
[19] Lothaire, M., Combinatorics on Words (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0874.20040
[21] Reutenauer, C., (Free Lie algebras. Free Lie algebras, London Math. Soc. Monographs New Ser., vol. 7 (1993), Oxford University Press), 288 pp. · Zbl 0798.17001
[22] Smyth, Bill, Computing Patterns in Strings (2003), Pearson, 423 pp.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.