pith. sign in

arxiv: 2604.26190 · v1 · submitted 2026-04-29 · 💻 cs.DS · cs.CL

Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings

Thomas Konstantinovsky , Gur Yaari This is my paper

Pith reviewed 2026-05-07 13:04 UTC · model grok-4.3

classification 💻 cs.DS cs.CL
keywords string decompositionrun-length encodingbilateral peelingreversible transformationrun pairingpalindrome characterisationlinear-time algorithm
0
0 comments X

The pith

Flashback decomposes any sentinel-wrapped string by repeatedly peeling its maximal leading and trailing runs, and this process is exactly equivalent to pairing the first run with the last, the second with the second-to-last, and so on.

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

The paper establishes a reversible bilateral decomposition called Flashback that peels maximal runs from both ends of a string and records each pair as a single token. It proves that this procedure always produces the same result as directly matching the outermost runs inward until the middle. The resulting token count is precisely one plus half the number of maximal runs, which matches the minimum possible for any scheme that peels from both sides. This equivalence immediately yields several structural facts about the decomposition, such as the form of its irreducible core and the characterization of palindromes.

Core claim

Flashback is equivalent to pairing the first run of the string with the last, the second with the second-to-last, and so on. This gives an exact token count of 1+[r/2] for a string with r maximal runs, and matches a lower bound that holds for any admissible bilateral run-peeling scheme. From the run-pairing theorem the main structural properties follow as corollaries: the irreducible peeling kernel uses at most two symbols; palindromes are precisely the strings whose run-length encoding is symmetric with an odd number of runs; the image of the decomposition admits an explicit finite-state characterisation; and changing one run length rewrites exactly one content token.

What carries the argument

The bilateral run-peeling step that removes one maximal leading run and one maximal trailing run (or the middle run when they meet) and records the pair as a single token, performed repeatedly until the string is empty.

If this is right

  • Any string with r maximal runs is represented by exactly 1 + floor(r/2) bilateral tokens.
  • The final irreducible kernel after all possible peels contains runs of at most two distinct symbols.
  • A string is a palindrome if and only if its run-length encoding is symmetric and contains an odd number of runs.
  • The set of all valid Flashback token sequences can be recognized by a finite-state automaton whose states track the current outer symbols.
  • Altering the length of any single run changes exactly one content token in the decomposition while leaving the others unchanged.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The pairing view suggests that Flashback could serve as a canonical normal form for comparing strings under bilateral symmetry operations.
  • Because reconstruction is also linear, the scheme supplies an explicit bijection between strings and their token sequences that preserves local run-length changes.
  • The finite-state characterisation of the image may allow efficient verification that a given sequence of tokens corresponds to some original string without performing the full reconstruction.

Load-bearing premise

The input must be wrapped by two distinct sentinel symbols that do not appear inside the string, and every peel step must select the current maximal runs at each end.

What would settle it

Any concrete string whose Flashback token sequence differs from the sequence obtained by directly listing the run pairs in outer-to-inner order.

Figures

Figures reproduced from arXiv: 2604.26190 by Gur Yaari, Thomas Konstantinovsky.

Figure 1
Figure 1. Figure 1: Bilateral peeling of CASSAYFF. Blue marks the leading run, red the trailing run, and grey the middle passed to the next depth. At each level the leading and trailing runs are removed together and emitted as one token; at d=3 the front and back runs cover the whole span, so the level emits a terminal token and the recursion stops. Proposition 4.4 (Nested spans). The active spans form a strictly decreasing c… view at source ↗
Figure 2
Figure 2. Figure 2: Run-pairing view of CASSAYFF. Each content token corresponds to one arc pairing two runs of the RLE (run j with run r + 1 − j); the middle run or two middle runs form the peeling kernel. The token count k = 1 + ⌈r/2⌉ of Theorem 6.2 counts the sentinel plus the arcs. Definition 6.3 (Admissible bilateral run-peeling). An admissible bilateral run-peeling decomposi￾tion of a non-empty string s is built by appl… view at source ↗
read the original abstract

We introduce Flashback, a reversible string decomposition that repeatedly peels the maximal leading and trailing character runs from a sentinel-wrapped input, recording each pair as one bilateral token. Decomposition and reconstruction both run in O(n) time and space. Our central result is a run-pairing theorem: Flashback is equivalent to pairing the first run of the string with the last, the second with the second-to-last, and so on. This gives an exact token count of 1+[r/2] for a string with r maximal runs, and matches a lower bound that holds for any admissible bilateral run-peeling scheme. From the run-pairing theorem the main structural properties follow as corollaries: the irreducible peeling kernel uses at most two symbols; palindromes are precisely the strings whose run-length encoding is symmetric with an odd number of runs; the image of the decomposition admits an explicit finite-state characterisation; and changing one run length rewrites exactly one content token.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The manuscript introduces Flashback, a reversible bilateral run-peeling decomposition for sentinel-wrapped strings. It repeatedly removes maximal leading and trailing runs, recording each pair as one token. The central result is a run-pairing theorem establishing equivalence to pairing the first run with the last, the second with the second-to-last, and so on. This yields an exact token count of 1 + ceil(r/2) for a string with r maximal runs and matches a lower bound for any admissible bilateral scheme. Decomposition and reconstruction are both O(n) in time and space. Corollaries include an irreducible kernel using at most two symbols, a characterization of palindromes via symmetric run-length encodings with odd run count, an explicit finite-state description of the image, and the property that altering one run length affects exactly one content token.

Significance. If the run-pairing theorem holds, the work supplies a simple, linear-time, reversible decomposition whose token count is combinatorially exact and optimal among admissible schemes. The matching lower bound and the clean corollaries on kernels, palindromes, and sensitivity to run-length edits give the result a self-contained combinatorial flavor that could be useful in run-length-based string algorithms, palindrome detection, and reversible data structures. The O(n) bounds and reversibility are practical assets.

minor comments (4)
  1. The abstract and introduction state the run-pairing theorem without a proof sketch or high-level derivation steps; adding a one-paragraph outline of the argument (e.g., by induction on the number of runs, using maximality and sentinel distinctness) would improve readability even if the full proof appears later.
  2. The weakest assumption (distinct sentinels and strictly maximal runs) is mentioned only briefly; a short paragraph or footnote clarifying why relaxing either condition can break the pairing equivalence would help readers assess the result's robustness.
  3. The finite-state characterisation of the image is listed as a corollary but receives no explicit automaton or transition table; including a compact diagram or state diagram would make this claim more concrete.
  4. No concrete small examples (e.g., a 5-run string and its token sequence) appear in the provided abstract or early sections; inserting one or two worked examples immediately after the theorem statement would aid intuition.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending minor revision. The summary accurately captures the introduction of Flashback, the run-pairing theorem, the exact token count, the O(n) bounds, and the listed corollaries on kernels, palindromes, finite-state characterization, and sensitivity to run-length changes.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The central run-pairing theorem is derived directly from the definition of the Flashback peeling process (repeated removal of maximal leading/trailing runs on sentinel-wrapped input) together with the invariant that maximality and distinct sentinels preserve the original run order without merges. This yields the outer-to-inner pairing and token count of 1 + ⌈r/2⌉ as an immediate structural consequence rather than a fitted quantity, self-citation, or imported uniqueness claim. All listed corollaries (kernel size, palindromes, finite-state image, single-run-length sensitivity) follow from the same process properties without circular reduction. The derivation is therefore self-contained as a standard equivalence proof in string algorithms.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions of strings and runs without introducing fitted parameters or new postulated entities.

axioms (2)
  • standard math A string is a finite sequence of characters drawn from a finite alphabet.
    Used throughout to define maximal runs and the sentinel wrapping.
  • domain assumption A maximal run is a longest contiguous substring of identical characters.
    Central to the peeling operation and the run-pairing equivalence.

pith-pipeline@v0.9.0 · 5463 in / 1374 out tokens · 44003 ms · 2026-05-07T13:04:32.115730+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

  1. [1]

    Taylor, David J

    Michael Burrows, D J Wheeler D I G I T A L, Robert W. Taylor, David J. Wheeler, and David Wheeler. A block-sorting lossless data compression algorithm. 1994

    work page 1994

  2. [2]

    Free differential calculus, IV

    K T Chen, R H Fox, and R C Lyndon. Free differential calculus, IV. the quotient groups of the lower central series.Ann. Math., 68(1):81, July 1958. 12

    work page 1958

  3. [3]

    On the complexity of finite sequences.IEEE Trans

    A Lempel and J Ziv. On the complexity of finite sequences.IEEE Trans. Inf. Theory, 22(1):75– 81, January 1976

    work page 1976

  4. [4]

    Factorizing words over an ordered alphabet.J

    Jean Pierre Duval. Factorizing words over an ordered alphabet.J. Algorithm., 4(4):363–381, December 1983

    work page 1983

  5. [5]

    Data compression via textual substitution.J

    James A Storer and Thomas G Szymanski. Data compression via textual substitution.J. ACM, 29(4):928–951, October 1982

    work page 1982

  6. [6]

    A universal algorithm for sequential data compression.IEEE Trans

    J Ziv and A Lempel. A universal algorithm for sequential data compression.IEEE Trans. Inf. Theory, 23(3):337–343, May 1977

    work page 1977

  7. [7]

    Compression of individual sequences via variable-rate coding.IEEE Trans

    J Ziv and A Lempel. Compression of individual sequences via variable-rate coding.IEEE Trans. Inf. Theory, 24(5):530–536, September 1978. A Supplementary Details A.1 Iterative Formulation of Decomposition SincePeelis tail-recursive (each invocation makes at most one recursive call, as the last operation), it admits a direct iterative rewrite: Algorithm 5Fl...

    work page 1978