{"id":"4c0169da-910a-449c-84ff-12b5f71f7add","arxiv_id":"1908.01664","paper_version":1,"verdict":"REJECT","confidence":"LOW","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper defines cyclic periodicity and cyclic covers and claims efficient algorithms, but the proofs are inadequate and one central test appears to reject a valid cyclic periodic string.","lead":"This paper claims fast new algorithms for finding rotated repeating blocks and covers in circular strings such as viral DNA. The proof sketches are too thin to support the claims, and a simple example appears to break the core periodicity test.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is falsified by x=abbaabba, k=2: the LCP check rejects a valid 2-cyclic periodic string, so the central algorithm is incorrect.","rationale":"The reader's rejection hinges on Theorem 1. I inspected Section 3's proof and the definition of k-cyclic periodicity. The counterexample x = abbaabba, k = 2 is decisive: the definition is satisfied by blocks (ab),(ba),(ab),(ba), each a rotation of (ab), yet the algorithm's first LCP check l_1 = LCP(x[1..8], x[4..8]) = 1 triggers the rejection branch. Thus the central characterization 'if l_m = 1 then not periodic' is false. Because Theorems 2 and 3 are obtained by running Theorem 1 for all k, their correctness inherits the flaw. The time bound O(n/k) also appears to ignore suffix-tree construction cost, but the correctness failure is the primary issue. The paper contains many typos and unhelpful tautological lemmas, but these are secondary to the false central algorithm. My proposed concrete test is a direct execution of the algorithm on this small instance; it settles the matter without relying on external assumptions. I agree with the reader's weakest_assumption and see no basis to change the REJECT verdict. This is an incorrect algorithm, not a matter of consensus or style.","tokens_in":4357,"tokens_out":5793,"duration_ms":55648,"concrete_test":"Run Theorem 1's procedure on x = abbaabba, k = 2: compute l_1 = LCP(x[1..8], x[4..8]); the value is 1, and the stated condition 'if l_m = 1 for some m, then x is not k-cyclic periodic' yields the answer false. Independently verify the definition: x decomposes into blocks ab, ba, ab, ba, each a rotation of ab, so the correct answer is true. If the implementation returns the algorithm's answer, the theorem is disproved; if it returns true, the condition was not implemented as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3, Theorem 1 claims an O(n/k) test for k-cyclic periodicity based on suffix-tree LCP depths. The proof asserts that if the LCP l_m between x[1..n] and x[i_m..n] equals 1 for any m, then x is not k-cyclic periodic. This characterization is not derived from the definition and is false. For x = abbaabba, k = 2, the definition is satisfied: x = (ab)(ba)(ab)(ba), each block is a rotation of (ab), so x is 2-cyclic periodic. However, x[1..8] and x[4..8] = aabba have LCP depth 1, so the algorithm would immediately classify x as not k-cyclic periodic. The root issue is that in a cyclic-periodic string, the block starting at i_m is a rotation of u, not u itself, so a short LCP between x and a suffix beginning at a block boundary does not indicate absence of cyclic periodicity. Theorems 2 and 3 invoke Theorem 1, so their correctness inherits this failure.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":4640,"tokens_out":7820,"duration_ms":67730,"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":[{"comment":"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":"Section 3, Theorem 1"},{"comment":"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":"Section 3, proof of Theorem 1"},{"comment":"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":"Section 4, Lemma 1, and Section 7, Lemma 3"},{"comment":"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.","section":"Section 6, Theorem 4"}],"minor_comments":[{"comment":"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":"Section 3, Theorem 1"},{"comment":"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":"Section 2, Example 4"},{"comment":"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.","section":"Section 2, Example 1"},{"comment":"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.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The counterexample to Theorem 1 is easy to verify and is not a matter of interpretive ambiguity; it directly contradicts the main algorithm. Given that the remaining theorems depend on Theorem 1 or on equally unsupported assertions, I do not see a local fix that would preserve the claimed results; a substantially rewritten paper with correct proofs would be needed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nWhat 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.","headline":"Fails on a two-block counterexample: the central test for cyclic periodicity is false, and the later results inherit the failure.","tokens_in":5102,"tokens_out":4243,"would_cite":false,"duration_ms":41286,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R15","68W32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["cyclic periodicity","cyclic covers","cyclic regularities","suffix tree","lowest common ancestor","string algorithms","maximal local periodicity"],"falsifier":"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.","tokens_in":4162,"feed_emoji":"🔄","tokens_out":7172,"duration_ms":67792,"temperature":0.7,"pith_summary":"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.","feed_headline":"Cyclic periodicity of strings: testable in O(n/k)","feed_subtitle":"A suffix-tree/LCA test decides whether a string repeats as rotated blocks; all cyclic periods then cost O(n log n).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the LCA query method used to obtain longest-common-prefix depths in O(1) after preprocessing.","marker":"[1]"},{"why":"Classic suffix-tree construction algorithm that the paper relies on to build T(x) in linear time.","marker":"[7]"},{"why":"Another linear-time suffix-tree construction, cited as the computation tool for the string's suffix tree.","marker":"[10]"},{"why":"Early linear-time suffix-tree construction, cited as the computation tool for the string's suffix tree.","marker":"[11]"}],"fun_headline_variants":["Suffix-tree LCA test cracks cyclic periods in O(n/k)","Cyclic periodic strings: linear-time detection via LCA","Efficient algorithms for all cyclic string regularities","Cyclic covers and periods: rapid via suffix-tree LCA"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Suffix-tree LCA test cracks cyclic periods in O(n/k)","Cyclic periodic strings: linear-time detection via LCA","Efficient algorithms for all cyclic string regularities","Cyclic covers and periods: rapid via suffix-tree LCA"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00071,"raw_usage":{"total_tokens":3122,"prompt_tokens":793,"completion_tokens":2329,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":409,"completion_tokens_details":{"reasoning_tokens":2261}},"tokens_in":409,"tokens_out":2329,"duration_ms":15140,"temperature":1.0,"reasoning_tokens":2261,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:07:02.998663+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"In: Latin American Symposium on Theoretical Informatics","cited_arxiv_id":null,"evidence_quote":"Supplies the LCA query method used to obtain longest-common-prefix depths in O(1) after preprocessing."},{"cited_title":"Journal of the ACM (JACM) 23(2), 262–272 (1976)","cited_arxiv_id":null,"evidence_quote":"Classic suffix-tree construction algorithm that the paper relies on to build T(x) in linear time."},{"cited_title":"In: Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture- Information Processing’92, Volume 1-Volume I","cited_arxiv_id":null,"evidence_quote":"Another linear-time suffix-tree construction, cited as the computation tool for the string's suffix tree."},{"cited_title":"In: 14th Annual Symposium on Switching and Automata Theory (swat 1973)","cited_arxiv_id":null,"evidence_quote":"Early linear-time suffix-tree construction, cited as the computation tool for the string's suffix tree."}],"review_version":1}