On the cyclic regularities of strings

Bruce Watson; Costas Iliopoulos; Jakub Radoszewski; Jia Gao; Mai Alzamel; Miznah Alshammary; Oluwole Ajala; Wojciech Rytter

REVIEW 4 major objections 4 minor 12 references

On the cyclic regularities of strings

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that k-cyclic periodicity of a length-n string can be tested in O(n/k) time using suffix-tree LCP queries, and that this test yields O(n log n) algorithms for all cyclic periodicities and maximal local cyclic…

desk verdict Fails on a two-block counterexample: the central test for cyclic periodicity is false, and the later results inherit the failure. read the letter →

arxiv 1908.01664 v1 pith:UUTN5QWU submitted 2019-08-05 cs.DS

Oluwole Ajala , Miznah Alshammary , Mai Alzamel , Jia Gao , Costas Iliopoulos , Jakub Radoszewski , Wojciech Rytter , Bruce Watson This is my paper · ORCID

classification cs.DS MSC 68R1568W32

keywords cyclicperiodicitycoversregularitiessuffixtreelowestcommonancestorstringalgorithmsmaximallocal

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that cyclic regularities—strings built from rotations of a single block—can be computed faster than by checking every rotation explicitly. Its central claim is a linear-time-construction, sublinear-per-block test: for any string of length n and block length k, deciding whether the string is k-cyclic periodic takes O(n/k) time after a suffix tree is built, because only the suffixes at positions 2k, 3k, ... need to be compared with the first block. If that test is sound, the paper's other results follow directly: all k can be tested in O(n log n), maximal local cyclic periodic factors in O(n log n), one cyclic cover in O(n), and all cyclic covers in O($n^{2}$). The motivation is biological: circular viral genomes, such as the E. coli chromosome, present the same sequence rotated at arbitrary break points, so cyclic periodicity is a natural regularity to detect. The O(n/k) theorem rests on an asserted characterization by longest-common-prefix depths; the later theorems inherit that premise.

What carries the argument

Suffix tree with LCA queries: after O(n) preprocessing, the length of the longest common prefix of any two suffixes is returned in O(1). The algorithm uses this on x to get l_m for suffixes starting at multiples of k, and on the reversed string to get l'_m comparing (u[l_m+1..k])^R with u^R. The work-carrying identity is the assertion l'_m ≥ l_m for all m iff x is k-cyclic periodic; this is what turns cyclic periodicity into a constant number of LCP comparisons per block boundary.

What would settle it

Run the Section 3 test on x = abbaabba with k = 2. The string is 2-cyclic periodic: ab · ba · ab · ba. The first LCP depth used by the algorithm, between x[1..8] and the suffix starting at position 2k = 4, is l_1 = 1 (first characters a match, second differ), and the proof states that l_m = 1 for any m means 'x is not k-cyclic periodic.' If the algorithm indeed rejects this string, the theorem's characterization is false; if a revised algorithm accepts it, the claimed O(n/k) test needs further machinery than the stated proof supplies.

Watch

Extended reading notes

Core claim

At the core is the claim that a string x of length n is k-cyclic periodic with u = x[1..k] exactly when certain suffix comparisons agree. The authors build the suffix tree of x (and x^R), use LCA queries to obtain l_m, the length of the longest common prefix of x and the suffix starting at i_m = 2k, 3k, ..., and then compare the reversed tail (u[l_m+1..k])^R against the reversed whole block u^R, obtaining l'_m. Their Theorem 1 asserts x is k-cyclic periodic iff l'_m ≥ l_m for every m; if any l_m equals 1 they reject. This yields O(n/k) time because the number of multiples is n/k and each LCA query costs O(1) after O(n) preprocessing. The remaining theorems repeat this test over all k or over all rotations to report all periods, maximal local factors, and covers.

Load-bearing premise

The proof of Theorem 1 assumes that comparing the prefix block u = x[1..k] against suffixes at positions 2k, 3k, ... by LCP depth, plus a symmetrized reversed comparison, is enough to certify that the whole string is k-cyclic periodic—if that equivalence fails for even one multiple of k, the O(n/k) test can reject a genuinely cyclic-periodic string.

Editorial extensions

If this is right

The k-cyclic periodicity test is the primitive: it runs in O(n/k), so the cost per candidate block shrinks as the block grows.
Running Theorem 1 for every k gives all cyclic periodicities of a length-n string in O(n log n) time and O(n) space (Theorem 2), matching the standard bound for detecting all ordinary periods.
The same O(n log n) bound covers maximal local k-cyclic periodic factors—substrings that are cyclic-periodic but cannot be extended by one character on either side (Theorem 3).
A length-k' cyclic cover, a block whose rotations cover every position of x, can be detected in O(n) time (Theorem 4), and all cyclic covers can be listed in O(n^2) time (Theorem 5).
For large k, the O(n/k) test is strictly faster than scanning the string once, so the cyclic tests are most valuable when blocks are long.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the LCP characterization is correct, cyclic periodicity is a much weaker regularity than ordinary periodicity: it asks only that each block align with one of k rotations, so testing many k values is cheap; an analogous cyclic-borders array could be derived from the same suffix tree.
The paper's use of only the suffix tree of x and x^R suggests a practical cross-check: for any k claimed non-periodic, test a few random rotations of x; if the same rejection pattern persists, that is evidence the characterization is stable under rotation, which Theorem 1 implicitly predicts.
A direct extension the paper leaves open is computing cyclic-periodic and cyclic-coverability arrays for every prefix; since all-prefix versions usually require O(n^2) data, the LCA machinery may only help if the characterization can be localized.
The biological motivation implies a practical application: if Theorem 1 holds, k-cyclic periodicity detection could be applied to circular genome segments to find rotation-invariant tandem structures.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This one you can skip. The paper's real novelty is the pair of definitions — k-cyclic periodicity and cyclic covers — as natural extensions of ordinary periods/covers to circular DNA. That idea is worth a sentence, but the algorithms built on top of it do not hold.

The main problem is Theorem 1. It claims an O(n/k) test for k-cyclic periodicity using suffix tree LCP depths. The proof asserts that if the LCP depth l_m between x and the suffix starting at a block boundary equals 1, then x is not k-cyclic periodic. That is simply false. Take x = abbaabba, k = 2. The string is 2-cyclic periodic because ab|ba|ab|ba has each block a rotation of ab. But x and the suffix starting at position 4 — aabba — share only the first character, so the theorem's check would reject it. The root issue is that a block in a cyclic periodic string need not match the prefix at all; it only needs to be a rotation of the same base word. So short LCP depth at a block boundary says nothing about absence of cyclic periodicity.

The rest of the paper does not compensate. Lemma 1 and Lemma 3 are tautological, and Theorem 4's coverability check is asserted with no real justification. The examples contain inconsistencies (Example 2's array values do not match the definition), and the text has numerous typos. Theorems 2 and 3 lean directly on Theorem 1, so they inherit the failure.

What is usably good here is modest but real: the concept of cyclic periodicity is clean enough to state, and the application to circular genomes is sensible. But the algorithmic contributions are not reconstructible, and the central theorem is contradicted by a two-block example. This does not deserve referee time as a research contribution. A desk reject is appropriate. If the authors can fix the characterization or drop the algorithmic claims, a cleaner version might be worth a look later.

Referee Report

4 major / 4 minor

Summary. The paper defines k-cyclic periodicity (a string decomposed into length-k blocks that are all rotations of one another) and cyclic coverability, and claims efficient algorithms: an O(n/k)-time decision test for k-cyclic periodicity, an O(n log n)-time computation of all cyclic periodicities, an O(n log n)-time computation of maximal local cyclic periodicities, an O(n)-time test for k'-cyclic coverability, and an O(n^2)-time computation of all cyclic covers. The central technical device is Theorem 1, which characterizes k-cyclic periodicity in terms of suffix-tree LCA depths between the whole string and suffixes starting at multiples of k.

Significance. If the claimed results were correct, the paper would contribute a useful family of linear-time-style algorithms for a natural class of string regularities with a plausible biological motivation. The definitions of cyclic periodicity and coverability are natural, and the intended use of suffix trees and LCA queries is a standard and potentially effective tool. However, the central characterization is false, and the paper supplies no correctness proof for the main test; the remaining theorems either inherit this failure or are supported only by assertion. There are no machine-checked proofs, reproducible code, or experimental results to compensate.

major comments (4)

[Section 3, Theorem 1] The condition 'if l_m = 1 for some m, then x is not k-cyclic periodic' is false. For x = abbaabba and k = 2, x = (ab)(ba)(ab)(ba), so every block is a rotation of the block ab and x is 2-cyclic periodic by the paper's definition. However, with i_m = 4, the LCP of x[1..8] = abbaabba and x[4..8] = aabba is exactly 1, so the algorithm would reject a valid instance. This demonstrates that a short LCP between the whole string and a suffix beginning at a block boundary does not negate cyclic periodicity, because the block starting at that boundary is a rotation of u, not u itself. Since Theorems 2 and 3 invoke Theorem 1, their correctness is consequently unsupported.
[Section 3, proof of Theorem 1] The proof asserts, without derivation, that the LCP conditions 'l_m = 1 implies not cyclic periodic' and 'l'_m >= l_m for all m implies k-cyclic periodic' are equivalent to the definition. The roles of u^R and Cright_m are introduced with no explanation of why reverse-prefix LCA comparisons certify that each block is a rotation of u, and no argument establishes sufficiency of the collected conditions. In particular, the proof does not explicitly handle blocks that are rotations different from u itself, which is exactly the case where the stated condition fails.
[Section 4, Lemma 1, and Section 7, Lemma 3] These lemmas are tautological: 'The smallest cyclic-period of x is the cyclic-period of x' and 'The smallest cyclic coverable of x is all the cyclic coverable of x' do not constitute algorithms or characterizations. Lemma 2's proof, 'We compute and merge the arrays for yα and βy of x', is likewise only a sketch. Since the paper presents these lemmas as part of the algorithmic contributions, the missing content is load-bearing for the claims in Sections 4, 5, and 7.
[Section 6, Theorem 4] The proof lists comparisons between x[1..k'] and suffixes x[n-k'+1..n], x[n-k'..n-1], ..., x[2..k'+1], 'together with the reverse pairs in T(x^R)', but it does not prove that this finite set of comparisons certifies that every position of x is covered by some rotation of u. It is also unclear how the reverse pairs are used, and the example that is supposed to illustrate the definition (Example 4) does not specify the parameters β and γ and introduces an unexplained 'gamma = 2'. Without a correctness argument, the claimed O(n) bound for k'-cyclic coverability is not established.

minor comments (4)

[Section 3, Theorem 1] There is a typo 'Crignt_m' that should read 'Cright_m'; the definitions of the depths l_m and l'_m are also imprecise, as they are described as 'depth of the lowest common ancestor' without stating that this is the string-depth used for LCP length.
[Section 2, Example 4] The example states 'k' = 4, gamma = 2' but gamma is never defined; the condition in Definition 3 requires specifying β and γ for each covered position.
[Section 2, Example 1] The sentence 'Therefore x has a period of length l' is confusing: with k = 4 and l = 4, the period length is k, not l; the intended meaning is that x consists of l cyclic blocks of length k.
[Throughout] The paper does not state the alphabet-size assumptions under which suffix-tree construction is O(n) time; for general integer alphabets this requires deterministic linear-time construction or randomization, and this should be made explicit in the complexity statements.

Circularity Check

3 steps flagged · score 3.0 of 10

Tautological lemmas and an unproved LCP characterization create circular presentation, but the main algorithms are not parameter-fitted or self-citation dependent.

self definitional [Section 4, Lemma 1]
"Lemma 1. Compute the cyclic period of x. . Proof. The smallest cyclic-period of x is the cyclic-period of x. ⊓ ⊔"

The lemma's proof is a verbatim restatement of the lemma itself: the object to be computed is asserted to be exactly that object. No algorithm, reduction, or characterization is supplied, so the statement carries no information beyond its own definition and cannot serve as a derived result.
self definitional [Section 7, Lemma 3]
"Lemma 3. Compute the cyclic coverability of x. . Proof. The smallest cyclic coverable of x is the all the cyclic coveralbe of x. ⊓ ⊔"

This is the same tautology as Lemma 1: the proof says the thing to be computed is itself. Even accounting for the typo 'coveralbe', there is no derivation, just the target restated. Like Lemma 1, it is peripheral to the main complexity theorems but is formally circular by construction.

1 more flagged steps

other [Section 3, Theorem 1 proof]
"We compute the LCA 𝓁_m of x[1..n] and x[i_m..n] for i_m = 2k, 3k,..., and 𝓁_k = n−k, if 𝓁_m = 1 for some m, then x is not k-cyclic periodic string. Now consider Crignt_m = (u𝓁m+1...uk)R, compute the 𝓁′_m the LCA of uR and Cright_m. If 𝓁′_m ≥ 𝓁_m for all m, then x is k-cyclic periodic."

The proof asserts an LCP-depth criterion as the decision procedure for k-cyclic periodicity, but it never derives this criterion from the earlier rotation-block definition. The theorem's correctness is thus assumed rather than established: the claimed derivation chain from the definition to the O(n/k) test is missing. This is an unsupported equivalence and a correctness risk, though not a parameter-fit circularity.

full rationale

The paper's main algorithmic claims are not circular in the data-fitting or self-citation sense: they rely on standard suffix-tree and LCA constructions as external machinery, and no parameter is fitted to a target answer. The two 'Compute the ...' lemmas (Lemmas 1 and 3) are pure tautologies, restating their own outputs as proofs; these are genuine but peripheral circular steps. The central concern is Theorem 1, whose proof asserts the LCP-condition characterization without deriving it from the definition of k-cyclic periodicity and which appears false for some strings; that is an omitted/faulty proof rather than a reduction of a prediction to an input. Because the tautological lemmas are not load-bearing and the main algorithms are built from independent standard tools, the circularity score is low-to-moderate rather than severe.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The main algorithms assume standard suffix tree and LCA primitives. The load-bearing nonstandard assumption is the characterization of k-cyclic periodicity by particular LCP depths (Theorem 1), which is unproved and apparently false. The coverability test in Theorem 4 depends on an unproved sufficiency of a limited set of suffix comparisons. No free parameters or invented entities are involved.

assumptions (3)

standard math Suffix trees for x and x^R can be constructed in linear time and answer LCA depth queries in constant time.
The paper invokes suffix tree construction [7,10,11] and LCA queries [1], both standard external results.
ad hoc to paper The LCP-depth conditions in Theorem 1 (l_m = 1 rejection and l'_m >= l_m acceptance) are equivalent to the definition of k-cyclic periodicity.
This equivalence is asserted in the proof of Theorem 1 without derivation and is contradicted by x = abbaabba, k = 2.
ad hoc to paper For cyclic coverability, checking x[1..k'] against suffixes x[n-k'+1..n], ..., x[2..k'+1] and their reverse pairs is sufficient to certify that every position is covered by a rotation.
Theorem 4's proof states this checking procedure without showing that it covers all positions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the cyclic regularities of strings." pith.science (2026). https://pith.science/paper/UUTN5QWU

@misc{pith2026190801664,
  author       = {Pith},
  title        = {Pith review of: On the cyclic regularities of strings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UUTN5QWU}},
  note         = {Machine review of arXiv:1908.01664}
}

read the original abstract

Regularities in strings are often related to periods and covers, which have extensively been studied, and algorithms for their efficient computation have broad application. In this paper we concentrate on computing cyclic regularities of strings, in particular, we propose several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers.

Figures

Figures reproduced from arXiv: 1908.01664 by the authors.

**Figure 1.** The E. coli K-12 MG1655 chromosome (outer black ring) was used as a reference map to visualise the locus position of 30 chromosome-borne CU fimbrial types. Types highlighted in blue are present in E. coli K-12 MG1655, types in red are absent in this strain. Fimbrial types associated with PAIs are indicated by an asterisk. A number of PAI associated fimbrial gene clusters occupy different locus positions relativ… view at source ↗

**Figure 2.** Circular Pattern. 2 Preliminaries A string x of length |x| = n over an alphabet Σ of size σ can be denoted as x[1 . . n] = x[1]x[2] . . . x[i] . . . x[n], where 1 ≤ i ≤ n and the i-th letter of x is denoted by x[i] ∈ Σ. The empty string is the string of length 0. The string x R is the reverse of string x. And x[i . . j], 1 ≤ i ≤ j ≤ n, denotes the contiguous substring (or factor) of letters, such as x[i]x[i + 1]x[… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

In: Latin American Symposium on Theoretical Informatics

Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Latin American Symposium on Theoretical Informatics. LNCS, vol. 1776, pp. 88–94. Springer- Verlag (2000)

work page 2000
[2]

Cambridge Uni- versity Press, New York, NY, USA (2007)

Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge Uni- versity Press, New York, NY, USA (2007)

work page 2007
[3]

Anti-Power Prefixes of the Thue-Morse Word

Defant, C.: Anti-power preﬁxes of the thue-morse word. arXiv preprint arXiv:1607.05825 (2016)

work page Pith review arXiv 2016
[4]

Erdős, P., et al.: Anti-ramsey theorems (1973)

work page 1973
[5]

Graphs and Combinatorics 26(1), 1–30 (2010)

Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of ramsey theory: a survey. Graphs and Combinatorics 26(1), 1–30 (2010)

work page 2010
[6]

Nucleic acids research 31(13), 3672–3678 (2003)

Kolpakov, R., Bana, G., Kucherov, G.: mreps: eﬃcient and ﬂexible detection of tandem repeats in dna. Nucleic acids research 31(13), 3672–3678 (2003)

work page 2003
[7]

Journal of the ACM (JACM) 23(2), 262–272 (1976)

McCreight, E.M.: A space-economical suﬃx tree construction algorithm. Journal of the ACM (JACM) 23(2), 262–272 (1976)

work page 1976
[8]

Narayanan,S.:Functionsonantipowerpreﬁxlengthsofthethue-morseword.arXiv preprint arXiv:1705.06310 (2017)

work page Pith review arXiv 2017

Show all 12 references

[9]

Norske Vid Selsk

Thue, A.: Uber unendliche zeichenreihen. Norske Vid Selsk. Skr. I Mat-Nat Kl.(Christiana) 7, 1–22 (1906)

1906
[10]

In: Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture- Information Processing’92, Volume 1-Volume I

Ukkonen, E.: Constructing suﬃx trees on-line in linear time. In: Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture- Information Processing’92, Volume 1-Volume I. pp. 484–492. North-Holland Pub- lishing Co. (1992)

1992
[11]

In: 14th Annual Symposium on Switching and Automata Theory (swat 1973)

Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory (swat 1973). pp. 1–11. IEEE (1973)

1973
[12]

PloS one 8(1), e52835 (2013)

Wurpel, D.J., Beatson, S.A., Totsika, M., Petty, N.K., Schembri, M.A.: Chaperone- usher ﬁmbriae of escherichia coli. PloS one 8(1), e52835 (2013)

2013

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

In: Latin American Symposium on Theoretical Informatics

Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Latin American Symposium on Theoretical Informatics. LNCS, vol. 1776, pp. 88–94. Springer- Verlag (2000)

work page 2000

[2] [2]

Cambridge Uni- versity Press, New York, NY, USA (2007)

Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge Uni- versity Press, New York, NY, USA (2007)

work page 2007

[3] [3]

Anti-Power Prefixes of the Thue-Morse Word

Defant, C.: Anti-power preﬁxes of the thue-morse word. arXiv preprint arXiv:1607.05825 (2016)

work page Pith review arXiv 2016

[4] [4]

Erdős, P., et al.: Anti-ramsey theorems (1973)

work page 1973

[5] [5]

Graphs and Combinatorics 26(1), 1–30 (2010)

Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of ramsey theory: a survey. Graphs and Combinatorics 26(1), 1–30 (2010)

work page 2010

[6] [6]

Nucleic acids research 31(13), 3672–3678 (2003)

Kolpakov, R., Bana, G., Kucherov, G.: mreps: eﬃcient and ﬂexible detection of tandem repeats in dna. Nucleic acids research 31(13), 3672–3678 (2003)

work page 2003

[7] [7]

Journal of the ACM (JACM) 23(2), 262–272 (1976)

McCreight, E.M.: A space-economical suﬃx tree construction algorithm. Journal of the ACM (JACM) 23(2), 262–272 (1976)

work page 1976

[8] [8]

Narayanan,S.:Functionsonantipowerpreﬁxlengthsofthethue-morseword.arXiv preprint arXiv:1705.06310 (2017)

work page Pith review arXiv 2017