Recognition: unknown
Subword enumeration up to stack-sorting equivalence
Pith reviewed 2026-05-07 15:33 UTC · model grok-4.3
The pith
Tortoise and hare repositioning rules extend abelian complexity to infinite words
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The tortoise and hare operations provide a natural way of extending abelian complexity functions for infinite sequences, in a way that gives light to structural properties associated with infinite words. Applied to the paperfolding word and the Thue-Morse word, the approach yields concrete structural information; in the Thue-Morse case it recovers a connection to earlier work on special factors. This supplies a basis for an interdisciplinary area that joins stack-sorting combinatorics with combinatorics on words.
What carries the argument
The tortoise and hare operations, which reposition repeated occurrences of the same character when generalizing the stack-sorting map from permutations to words.
If this is right
- The extension applies to the paperfolding word and produces new information about its subword structure.
- For the Thue-Morse word the measure recovers a connection to its special factors.
- Subword enumeration becomes possible up to stack-sorting equivalence defined by the repositioning rules.
- The construction supplies a concrete bridge between permutation combinatorics and the theory of infinite words.
Where Pith is reading between the lines
- The same operations could be tested on other automatic sequences to check whether they consistently illuminate factor structure.
- Enumeration algorithms for subwords up to this equivalence might be implemented by simulating the tortoise and hare moves.
- The resulting complexity functions may turn out to be computable from the morphism generating the infinite word.
Load-bearing premise
That the tortoise and hare repositioning rules form a natural and structurally revealing extension of abelian complexity rather than an arbitrary redefinition.
What would settle it
A direct computation of the extended complexity function on the Thue-Morse word that fails to recover or relate to the known counts and positions of its special factors would falsify the claimed structural link.
read the original abstract
Defant and Kravitz introduced generalizations of West's stack-sorting map $s$ from permutations to finite words. This raises questions as to how such generalizations could be applied in the field of combinatorics on words. The Defant-Kravitz generalizations of $s$ depend on how repeated occurrences of the same character within a word may be repositioned, according to their $\textsf{tortoise}$ and $\textsf{hare}$ operations. As demonstrated in this paper, these operations provide a natural way of extending abelian complexity functions for infinite sequences, in a way that gives light to structural properties associated with infinite words. We apply these new ideas to two famous infinite words: the paperfolding word and the Thue-Morse word. In the case of the Thue-Morse word, we discover an interesting connection to the previous work of several authors, such as de Luca and Varricchio, on the ``special'' factors of the Thue-Morse word. This may be seen as providing a basis for a new and interdisciplinary area linking the combinatorics about the stack-sorting of permutations with the field of combinatorics on words.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes using the tortoise and hare repositioning operations from Defant and Kravitz's generalizations of West's stack-sorting map to extend abelian complexity functions from finite words to infinite sequences. It defines the associated subword enumeration functions based on these operations, computes them explicitly for the paperfolding word and the Thue-Morse word, and recovers known results on the special factors of the Thue-Morse word while suggesting an interdisciplinary connection between stack-sorting combinatorics and combinatorics on words.
Significance. If the definitions are accepted, the work supplies a concrete bridge between two combinatorial domains by repurposing stack-sorting repositioning rules as a tool for measuring structural properties of infinite words. The recovery of existing facts about Thue-Morse special factors serves as an internal consistency check, and the explicit computations on standard aperiodic words provide a reproducible starting point for further exploration at the intersection of the fields.
minor comments (3)
- The abstract states that the operations 'provide a natural way' of extending abelian complexity but does not preview the precise definition of the new complexity function (e.g., how factors are counted up to tortoise/hare equivalence); adding one sentence with the formal definition would improve accessibility.
- In the section applying the construction to the Thue-Morse word, the link to de Luca-Varricchio special factors is asserted via recovery of known facts; a short table or explicit enumeration showing which factors are distinguished by the new function versus the classical abelian complexity would make the claimed structural insight more transparent.
- Notation for the tortoise and hare operations is introduced via reference to Defant-Kravitz; a self-contained one-paragraph recap of the repositioning rules (with a small example on a short word) would reduce dependence on the external reference for readers primarily interested in combinatorics on words.
Simulated Author's Rebuttal
We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. We appreciate the recognition of the interdisciplinary link between generalized stack-sorting operations and abelian complexity for infinite words, as well as the consistency check via the Thue-Morse special factors.
Circularity Check
No significant circularity identified
full rationale
The manuscript introduces explicit definitions for new abelian complexity functions on infinite words by applying the tortoise and hare repositioning rules from Defant-Kravitz stack-sorting generalizations. It then directly computes the resulting subword enumerations for the paperfolding and Thue-Morse words, recovering previously known facts about special factors of the Thue-Morse word. No fitted parameters, predictions that reduce to inputs by construction, self-citations that bear the central claim, or uniqueness theorems appear. The contribution is a definitional bridge followed by explicit calculation and is therefore self-contained.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard definitions of West stack-sorting, tortoise and hare operations, and abelian complexity from prior literature
Reference graph
Works this paper leans on
-
[1]
Allouche, The number of factors in a paperfolding sequence, Bull
[1]J.-P. Allouche, The number of factors in a paperfolding sequence, Bull. Austral. Math. Soc.46(1)(1992), 23–32. [2]J.-P. Allouche and M. Bousquet-M ´elou, Facteurs des suites de Rudin-Shapiro g´ en´ eralis´ ees,Bull. Belg. Math. Soc. Simon Stevin1(2) (1994), 145–164. [3]J.-P. Allouche and J. Shallit, Automatic sequences, Cambridge University Press, Camb...
1992
-
[2]
Brlek, Enumeration of factors in the Thue-Morse word,Discrete Appl
[6]S. Brlek, Enumeration of factors in the Thue-Morse word,Discrete Appl. Math.24(1-3)(1989), 83–96. [7]J. Cassaigne, Special factors of sequences with linear subword com- plexity, inDevelopments in language theory, II (Magdeburg, 1995), 25– 34, World Sci. Publ., River Edge, NJ (1996). [8]J. Cassaigne, G. Fici, M. Sciortino, and L. Q. Zamboni, Cyclic comp...
1989
-
[3]
Defant, Descents int-sorted permutations,J
[12]C. Defant, Descents int-sorted permutations,J. Comb.11(3)(2020), 511–526. [13]C. Defant, Fertility, strong fertility, and postorder Wilf equivalence, Australas. J. Combin.76(2020), 149–182. [14]C. Defant, Fertility numbers,J. Comb.11(3)(2020), 527–548. [15]C. Defant, Polyurethane toggles,Electron. J. Combin.27(2)(2020), Paper No. 2.46,
2020
-
[4]
Defant, Proofs of conjectures about pattern-avoiding linear exten- sions,Discrete Math
[16]C. Defant, Proofs of conjectures about pattern-avoiding linear exten- sions,Discrete Math. Theor. Comput. Sci.21(4)(2019), Paper No. 16,
2019
-
[5]
Defant, M
[17]C. Defant, M. Engen, and J. A. Miller, Stack-sorting, set par- titions, and Lassalle’s sequence,J. Combin. Theory Ser. A175(2020), 105275,
2020
-
[6]
Defant and N
21 [18]C. Defant and N. Kravitz, Foot-sorting for socks,Electron. J. Com- bin.31(3)(2024), Paper No. 3.5,
2024
-
[7]
Defant and N
[19]C. Defant and N. Kravitz, Stack-sorting for words,Australas. J. Combin.77(2020), 51–68. [20]G. Fici and S. Puzynina, Abelian combinatorics on words: a survey, Comput. Sci. Rev.47(2023), Paper No. 100532,
2020
-
[8]
Golafshan, M
[21]M. Golafshan, M. Rigo, and M. A. Whiteland, Computing the k-binomial complexity of generalized Thue-Morse words,J. Combin. Theory Ser. A220(2026), Paper No. 106152,
2026
-
[9]
Karhum ¨aki, Generalized Parikh mappings and homomorphisms, Inform
[22]J. Karhum ¨aki, Generalized Parikh mappings and homomorphisms, Inform. and Control47(3)(1980), 155–165. [23]D. E. Knuth, The art of computer programming, I: Fundamental al- gorithms, vol. 1, AddisonWesley, Reading, MA (1973). [24]M. Lejeune, J. Leroy, and M. Rigo, Computing thek-binomial complexity of the Thue-Morse word,J. Combin. Theory Ser. A176 (2...
1980
-
[10]
[25]X.-T. L ¨u, J. Chen, Z.-X. Wen, and W. Wu, On the 2-binomial complexity of the generalized Thue-Morse words,Theoret. Comput. Sci. 986(2024), Paper No. 114342,
2024
-
[11]
de Luca and S
[26]A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups,Theoret. Comput. Sci.63(3)(1989), 333–348. [27]B. Madill and N. Rampersad, The abelian complexity of the pa- perfolding word,Discrete Math.313(7)(2013), 831–838. [28]M. Morse and G. A. Hedlund, Symbolic dynamics II. Sturmian trajectories,...
1989
-
[12]
West, Permutations with forbidden subsequences and stack-sortable permutations, Thesis (Ph.D.)–Massachusetts Institute of Technology (1990)
[32]J. West, Permutations with forbidden subsequences and stack-sortable permutations, Thesis (Ph.D.)–Massachusetts Institute of Technology (1990). John M. Campbell Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia, B3H 4R2, Canada jh241966@dal.ca Narad Rampersad Department of Mathematics and Statistics University of Winni...
1990
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.