The DOI matches its Crossref record; 62 of the 62 references it cites were found in a registry or an index; none of the 29 sources its claims cite is checked for support yet.
Longest Gapped Repeats and Palindromes
Open accessAbstract
A gapped repeat (respectively, palindrome) occurring in a word $w$ is a factor $uvu$ (respectively, $u^Rvu$) of $w$. In such a repeat (palindrome) $u$ is called the arm of the repeat (respectively, palindrome), while $v$ is called the gap. We show how to compute efficiently, for every position $i$ of the word $w$, the longest gapped repeat and palindrome occurring at that position, provided that the length of the gap is subject to various types of restrictions. That is, that for each position $i$ we compute the longest prefix $u$ of $w[i..n]$ such that $uv$ (respectively, $u^Rv$) is a suffix of $w[1..i-1]$ (defining thus a gapped repeat $uvu$ -- respectively, palindrome $u^Rvu$), and the length of $v$ is subject to the aforementioned restrictions. Comment: This is an extension of the conference papers "Longest $\alpha$-Gapped Repeat and Palindrome", presented by the second and third authors at FCT 2015, and "Longest Gapped Repeats and Palindromes", presented by the first and third authors at MFCS 2015
Overview
CoChat Summary
TL;DR
The paper gives algorithms to construct longest previous gapped repeat/palindrome tables for each position of a word under several gap restrictions. It obtains linear or near-linear bounds for bounded-gap and position-dependent lower bounds, and \(O(\alpha n)\) bounds for \(\alpha\)-gapped repeats and palindromes.
Key findings
- For gap length between \(g\) and \(G\), the longest previous reverse-factor array \(LPrF_{g,G}[\cdot]\) can be built in \(O(n)\) time, while the longest previous factor array \(LPF_{g,G}[\cdot]\) can be built in \(O(n\log n)\) time; consequently the longest gapped palindrome is found in linear time and the longest gapped repeat in \(O(n\log n)\) time.
- For a position-dependent lower bound \(g(i)\), both \(LPrF_g[\cdot]\) and \(LPF_g[\cdot]\) can be constructed in linear time, and the longest gapped palindrome or repeat satisfying \(|v|\ge g(i)\) is found in linear time.
- For \(\alpha\)-gapped repeats \(uvu\) and palindromes \(u^Rvu\) with \(|uv|\le \alpha |u|\), the arrays \(LRep_\alpha[\cdot]\) and \(LPal_\alpha[\cdot]\) can be constructed in \(O(\alpha n)\) time; the longest such repeat or palindrome can also be found in \(O(\alpha n)\) time.
- The paper notes that the number of maximal \(\alpha\)-gapped repeats or palindromes is \(\Theta(\alpha n)\), and it uses algorithms from prior work that find all such maximal structures in optimal \(\Theta(\alpha n)\) time.
Methods
- The algorithms are string-data-structure based, using suffix arrays, LCP queries, dictionaries of basic factors, runs, interval union-find structures, and weighted level ancestor queries; for palindromes, suffix arrays are built for \(w0w^R\).
- For Problem 1(a), a sliding window over ranges of length \(\delta=G-g\) and interval union-find give linear time; Problem 1(b) splits by arm length \(2^k\), uses basic-factor occurrence representations, and runs in \(O(n\log n)\).
- Problem 2 is reduced to maintaining ordered lists via \(L^+[i]\) chains and solving offline union-find/weighted-level-ancestor queries in linear time; Problem 3 uses block encodings, lemmas for compact occurrence reporting, and the set of all maximal \(\alpha\)-gapped repeats/palindromes to compute the arrays in \(O(\alpha n)\).
Limitations
- Stated in the paper: it remains open whether Problem 1(b) can be solved faster, whether the longest gapped repeats with gap between \(g\) and \(G\) can be found in linear time, whether the longest \(\alpha\)-gapped repeat or palindrome can be found faster than \(O(\alpha n)\), and whether the Problem 3 arrays can be constructed without first producing all maximal \(\alpha\)-gapped repeats and palindromes.
- Evident from the text: no implementation or empirical evaluation is reported; the results are asymptotic and rely on the unit-cost RAM with logarithmic word size and integer-alphabet assumptions.
- Evident from the text: the bounded-gap repeat table \(LPF_{g,G}[\cdot]\) has \(O(n\log n)\) complexity, so it is not linear like the corresponding palindrome table.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Figures


![Fig. 3 Proof of Theorem 2: Occurrences of w [ i..i + 2 k -1] inside w [ i -G -2 k +1 ..i -g -1] : one separate occurrence, and a run containing three occurrences. The separate occurrence can be prolonged to produce a gapped palindrome uvu , which is not, however, long enough as it does not reach the range between i -G and i -g . The rightmost occurrence in the run produces the gapped repeat w [ i..i + 2 k -1] v ′ w [ i..i + 2 k -1] , which fulfils the conditions imposed on the gap.](/paper-figures/8313bed4c8144cadb213c5accb8aba27/longest-gapped-repeats-and-palindromes-figure-3.png)




Verification
Claims the paper makes
0 Valid · 5 Not valid · 27 Not checked · 89 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Similarly to the previous cases, we check in O ( α ) time which is the longest α -gapped repeat obtained by pairing one of these occurrences to y , and extending them similarly to the left and right.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Theorem 2 Problem 1(b) can be solved in O ( n log n ) time.”
plainn = 2- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The algorithm computes H [ · ] correctly. Indeed, we set H [ ℓ ] = g when we process an interval I j of weight g that contains ℓ , and no other interval of greater weight contained ℓ .”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“This shows that the total number of find operations is O ( k + | ∪ j =1 ,k I j | ) = O ( n + k ) .”
boostedstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The right arm u 2 of such a repeat is contained in a factor w [ m log n +1 .. ( m +17)log n ] of w , while u 1 surely occurs in a factor x = w [ m log n -16 α log n +1 .. ( m +17)log n ] (or, if m log n -16 α log n + 1 ≤ 0 , then in a factor x = w [1 .. ( m + 17) log n ] ); in total, there are O ( n/ log n ) such x factors.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
85 more claims
Create a free account to see all 121 claims and to verify the 17 references still open.
- It may state two separate claims as one. 13
- The quote only partly states this claim. 3
- Probably not a substantial claim. 18
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 1 Introduction · p. 2
“with g ≤ | v | < G”
§ 1 Introduction · p. 2
“with g < | v | ≤ G”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 4 Lower bounded gap · p. 18
“Lemma 6 Given a word w , let L [ i ] = min { j | j < i, LCP ( j, i ) ≥ LCP ( k, i ) for all k < i } .”
§ 4 Lower bounded gap · p. 18
“L [ i ] = B > [ i ] if LCP ( B > [ i ] , i ) > LCP ( B < [ i ] , i ) or LCP ( B > [ i ] , i ) = LCP ( B < [ i ] , i ) and B > [ i ] > B < [ i ]”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 3 Lower and upper bounded gap · p. 13
“Clearly, knowing B [ i ] means knowing LPrF g,G [ i ] .”
§ 3 Lower and upper bounded gap · p. 13
“Theorem 2 Problem 1(b) can be solved in O ( n log n ) time.”
Citations
Cites
Grossman, P. (2009) · Discrete Mathematics for Computing · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,834
Fast Pattern Matching in Strings
Knuth, D. E., Morris, Jr., & Pratt, V. R. (1977) · SIAM Journal on Computing · doi:10.1137/0206024 · Cited by 2,936
The Art of Computer Programming. Volume 1: Fundamental Algorithms.
Odeh, R. E., & Knuth, D. E. (1969) · Journal of the American Statistical Association · doi:10.2307/2283757 · Cited by 2,525
The Art of Computer Programming
Worlton, W. J. (1968) · Nuclear Science and Engineering · doi:10.13182/nse68-a19548 · Cited by 2,251
Lothaire, M. (1984) · HAL · Cited by 1,753
Introduction to Analytic Number Theory
Apostol, T. M. (1976) · Undergraduate texts in mathematics · doi:10.1007/978-1-4757-5579-4 · Cited by 1,583
Bender, M. A., & Farach-Colton, M. (2000) · Lecture notes in computer science · doi:10.1007/10719839_9 · Cited by 815
Crochemore, M., Hancart, C., & Lecroq, T. (2007) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546853 · Cited by 676
Finding patterns common to a set of strings
Angluin, D. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90041-0 · Cited by 616
Chan, S. R. W. L., & Blackburn, E. H. (2004) · Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rstb.2003.1370 · Cited by 595
Optimal suffix tree construction with large alphabets
Farach, M. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646102 · Cited by 443
Linear work suffix array construction
Kärkkäinen, J., Sanders, P., & Burkhardt, S. (2006) · Journal of the ACM · doi:10.1145/1217856.1217858 · Cited by 433
Trans-dichotomous algorithms for minimum spanning trees and shortest paths
Fredman, M. L., & Willard, D. E. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80064-9 · Cited by 419
Choffrut, C., & Karhumäki, J. (1997) · Springer eBooks · doi:10.1007/978-3-642-59136-5_6 · Cited by 350
Jewels of Stringology: Text Algorithms
Crochemore, M., & Rytter, W. (2002) · WORLD SCIENTIFIC eBooks · doi:10.1142/4838 · Cited by 345
Finding maximal repetitions in a word in linear time
Kolpakov, R. M., & Kucherov, G. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814634 · Cited by 338
An optimal algorithm for computing the repetitions in a word
Crochemore, M. (1981) · Information Processing Letters · doi:10.1016/0020-0190(81)90024-7 · Cited by 315
Preserving order in a forest in less than logarithmic time
Boas, P. V. E. (1975) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1975.26 · Cited by 203
Partial words and a theorem of Fine and Wilf
Jean Berstel, A., & Boasson, L. (1999) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00255-2 · Cited by 169
A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String
Manacher, G. K. (1975) · Journal of the ACM · doi:10.1145/321892.321896 · Cited by 153
Computing Longest Previous Factor in linear time and applications
Crochemore, M., & Ilie, L. (2007) · Information Processing Letters · doi:10.1016/j.ipl.2007.10.006 · Cited by 152
Some Asymptotic Expressions in the Theory of Numbers
Gronwall, T. H. (1913) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1913-1500940-6 · Cited by 148
Detecting leftmost maximal periodicities
Main, M. G. (1989) · Discrete Applied Mathematics · doi:10.1016/0166-218x(89)90051-6 · Cited by 114
A linear-time algorithm for a special case of disjoint set union
Gabow, H. N., & Tarjan, R. E. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808753 · Cited by 94
Searching for gapped palindromes
Kolpakov, R. M., & Kucherov, G. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2009.09.013 · Cited by 64
Fine and Wilf's Theorem for Abelian Periods.
Constantinescu, S., & Ilie, L. (2006) · Bulletin of the European Association for Theoretical Computer Science · Cited by 58
Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
Crochemore, M., & Rytter, W. (1991) · Theoretical Computer Science · doi:10.1016/0304-3975(91)90073-b · Cited by 53
On a special class of primitive words
Czeizler, E., Lila Kari, A., & Seki, S. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2009.09.037 · Cited by 48
Finding repeats with fixed gap
Kolpakov, R. M., & Kucherov, G. (2002) · String Processing and Information Retrieval · doi:10.1109/spire.2000.878192 · Cited by 47
Computing Longest Previous non-overlapping Factors
Crochemore, M., & Tischler, G. (2010) · Information Processing Letters · doi:10.1016/j.ipl.2010.12.005 · Cited by 33
Searching of Gapped Repeats and Subrepetitions in a Word
Kolpakov, R. M., Podolskiy, M., Posypkin, M. A., & Павлович, Х. Н. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07566-2_22 · Cited by 28
A new characterization of maximal repetitions by Lyndon trees
Bannai, H., Tomohiro, I., Inenaga, S., Nakashima, Y., Takeda, M., & Tsuruta, K. (2014) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973730.38 · Cited by 28
Computing the Longest Previous Factor
Crochemore, M., Ilie, L., Iliopoulos, C. S., Kubica, M., Rytter, W., & Waleń, T. (2012) · European Journal of Combinatorics · doi:10.1016/j.ejc.2012.07.011 · Cited by 26
A new characterization of maximal repetitions by Lyndon trees
Bannai, H., Tomohiro, I., Inenaga, S., Nakashima, Y., Masayuki, T., & Tsuruta, K. (2014) · IEICE Technical Report; IEICE Tech. Rep. · Cited by 26
Generalised fine and Wilf's theorem for arbitrary number of periods
Constantinescu, S., & Ilie, L. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.01.007 · Cited by 23
Lempel-Ziv Factorization May Be Harder Than Computing All RunsPreprint
Kosolobov, D. (2014) · arXiv (Cornell University) · doi:10.4230/lipics.stacs.2015.582 · Cited by 23
Testing Generalised Freeness of Words
Gawrychowski, P., Manea, F., & Nowotka, D. (2014) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2014.337 · Cited by 21
Self-citationGawrychowski, P., Manea, F., Mercaş, R., Nowotka, D., & Tiseanu, C. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2013.257 · Cited by 20
Self-citationFine and Wilf’s Theorem and Pseudo-repetitions
Manea, F., Mercaş, R., & Nowotka, D. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32589-2_58 · Cited by 18
Self-citationPattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
Gawrychowski, P. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-23719-5_36 · Cited by 18
Self-citationComputation of squares in a string: Preliminary version
Kosaraju, S. R. (1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-58094-8_13 · Cited by 17
A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String
Tanimura, Y., Fujishige, Y., Tomohiro, I., Inenaga, S., Bannai, H., & Takeda, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-23826-5_13 · Cited by 17
Chiniforooshan, E., Lila Kari, A., & Xu, Z. (2012) · Fundamenta Informaticae · doi:10.3233/fi-2011-617 · Cited by 17
Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
Crochemore, M., Kolpakov, R. M., & Kucherov, G. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-30000-9_19 · Cited by 17
Searching for Gapped Palindromes
Kolpakov, R. M., & Kucherov, G. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-69068-9_5 · Cited by 15
The Avoidability of Cubes under Permutations
Manea, F., Müller, M., & Nowotka, D. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31653-1_37 · Cited by 13
Self-citationAn Improved Bound for an Extension of Fine and Wilf’s Theorem and Its Optimality
Lila Kari, A., & Seki, S. (2010) · Fundamenta Informaticae · doi:10.3233/fi-2010-285 · Cited by 12
Discovering Hidden Repetitions in Words
Gawrychowski, P., Manea, F., & Nowotka, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39053-1_24 · Cited by 12
Self-citationA minimal periods algorithm with applicationsPreprint
Xu, Z. (n.d.) · Cited by 12
Efficient Data Structures for the Factor Periodicity Problem
Kociumaka, T., Radoszewski, J., Rytter, W., & Waleń, T. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-34109-0_30 · Cited by 11
Optimal searching of gapped repeats in a wordPreprint
Crochemore, M., Kolpakov, R. M., & Kucherov, G. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.01221 · Cited by 6
Longest $$\alpha $$-Gapped Repeat and Palindrome
Gawrychowski, P., & Manea, F. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-22177-9_3 · Cited by 6
Self-citationLinear-Time Computation of Local Periods
Duval, J.-P., Kolpakov, R., Kucherov, G., Lecroq, T., & Lefebvre, A. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45138-9_33 · Cited by 2
Efficient algorithms for two extensions of LPF table: the power of suffix arrays
Crochemore, M., Iliopoulos, C. S., Kubica, M., Rytter, W., & Waleń, T. (2010) · HAL · Cited by 2
Finding Maximal Pairs with Bounded Gap
Brodal, G. S., Lyngsø, R. B., Pedersen, C. N. S., & Stoye, J. (1999) · BRICS Report Series · doi:10.7146/brics.v6i12.20069 · Cited by 1
(1997)
Efficiently Finding All Maximal alpha-gapped Repeats
Gawrychowski, P., I, T., Inenaga, S., Köppl, D., & Manea, F. (2016) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.stacs.2016.39
Self-citationFinding Maximal Pairs with Bounded Gap
Brodal, G. S., Lyngsø, R. B., Pedersen, C. N. S., & Stoye, J. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48452-3_11
Squares, cubes, and time-space efficient string searching
Crochemore, M., & Rytter, W. (1995) · Algorithmica · doi:10.1007/bf01190846
Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
Crochemore, M., Iliopoulos, C. S., Kubica, M., Rytter, W., & Waleń, T. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-11266-9_25
Longest Gapped Repeats and Palindromes
Dumitran, M., & Manea, F. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-48057-1_16
Self-citationBannai, H., Tomohiro, I., Inenaga, S., Nakashima, Y., Takeda, M., & Tsuruta, K. (2014) · arXiv · doi:10.48550/arxiv.1406.0263
Research works printed but not linked: 3
- A. Ehrenfeucht and G. Rozenberg. Finding a Homomorphism Between Two Words is NP-Complete. Inf. Process. Lett. , 9(2):86-88, 1979.
- N. J. Fine and H. S. Wilf. Uniqueness theorem for periodic functions. Proceedings of the American Mathematical Society , 16:109-114, 1965.
- J. Justin. On a paper by Castelli, Mignosi, Restivo. ITA , 34(5):373-377, 2000.
Cited by
Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
Crochemore, M., Kolpakov, R. M., & Kucherov, G. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-30000-9_19 · Cited by 17
Efficient representation and counting of antipower factors in words
Kociumaka, T., Radoszewski, J., Rytter, W., Straszyński, J., Waleń, T., & Zuba, W. (2021) · Information and Computation · doi:10.1016/j.ic.2021.104779 · Cited by 9
Optimal searching of gapped repeats in a wordPreprint
Crochemore, M., Kolpakov, R. M., & Kucherov, G. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.01221 · Cited by 6
On the number of gapped repeats with arbitrary gap
Kolpakov, R. M. (2018) · Theoretical Computer Science · doi:10.1016/j.tcs.2018.03.007 · Cited by 5
Reversed Lempel–Ziv Factorization with Suffix Trees
Köppl, D. (2021) · Algorithms · doi:10.3390/a14060161 · Cited by 2
Metadata
- Authors
- Dumitran, M., Gawrychowski, P., & Manea, F.
- Affiliations
- University of Wrocław (PL)
- ORCID
- Gawrychowski, Paweł
- Venue
- Discrete Mathematics & Theoretical Computer Science
- Published
- 2017-10-13
- Volume
- Vol. 19 no. 4, FCT '15
- Issue
- special issue FCT'15
- ISSN
- 1365-8050 (ISSN-L)
- OpenAlex
- W2950226630
- Cited by
- 11
- References
- 55
- Citations by year
- 2025: 1 · 2021: 4 · 2019: 1 · 2018: 2
- FWCI
- 0.84
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (am)
- creativecommons.org/licenses/by/4.0 (vor)
- creativecommons.org/licenses/by/4.0 (tdm)
- Locations
- Discrete Mathematics & Theoretical Computer Science (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, cc-by)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- arXiv (Cornell University) (cc-by)
- Entrepôt pour orphelin (cc-by-nd)
- Discrete Mathematics & Theoretical Computer Science (cc-by)
- Funders
- Deutsche Forschungsgemeinschaft (596676)
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
- Keywords
- palindromes, string algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-11-14, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-11-14 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.