Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings

• URL: http://arxiv.org/abs/2604.26190v1
• Date: Wed, 29 Apr 2026 00:30:33 GMT
• Title: Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings
• Abstract summary: Flashback is a reversible string decomposition that repeatedly peels the maximal leading and trailing character runs from a sentinel-wrapped input.<n>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.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Comments on the recent improvements of the MRRW bounds [59.04174294928297]
  We present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.<n>We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.
  arXiv  Detail & Related papers  (2026-09-01T20:43:23Z)
• Fast Bounded-Independence Functions and Their Duals [21.031497777539332]
  Motivated by cryptographic applications, we generalize and improve on previous results in this area.<n>We demonstrate the usefulness of the above results to cryptography.<n>This includes the first nontrivial protocols for perfectly secure multiparty computation.
  arXiv  Detail & Related papers  (2026-06-05T07:53:04Z)
• Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees [68.04613115686509]
  Self-consistency boosts inference-time performance by sampling multiple reasoning traces in parallel and voting.<n>We propose Distinct Leafion (DLE), a deterministic decoding method that treats truncated sampling as a pruned tree and systematically enumerates distinct leaves instead of sampling with replacement.<n>DLE explores higher-quality reasoning traces, yielding better performance on math, coding, and general reasoning tasks.
  arXiv  Detail & Related papers  (2026-04-22T12:42:03Z)
• Rainbow Padding: Mitigating Early Termination in Instruction-Tuned Diffusion LLMs [10.214443153276962]
  Diffusion large language models exhibit a critical vulnerability we term textteos> overflow.<n>We introduce Rainbow Padding, a simple remedy that replaces repeated textteos> placeholders with a repeating cycle of distinct padding tokens.<n>Experiments show that Rainbow Padding substantially improves length robustness and output quality, with as few as seven padding tokens sufficient to prevent early termination.
  arXiv  Detail & Related papers  (2025-10-04T05:24:27Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string.
  arXiv  Detail & Related papers  (2023-05-24T11:47:35Z)
• Reducing Discontinuous to Continuous Parsing with Pointer Network Reordering [0.7412445894287709]
  A discontinuous tree can be converted into a continuous variant by reordering tokens. We develop a Pointer Network capable of accurately generating the continuous token arrangement for a given input sentence.
  arXiv  Detail & Related papers  (2021-04-13T14:32:59Z)
• Context-aware and Scale-insensitive Temporal Repetition Counting [60.40438811580856]
  Temporal repetition counting aims to estimate the number of cycles of a given repetitive action. Existing deep learning methods assume repetitive actions are performed in a fixed time-scale, which is invalid for the complex repetitive actions in real life. We propose a context-aware and scale-insensitive framework to tackle the challenges in repetition counting caused by the unknown and diverse cycle-lengths.
  arXiv  Detail & Related papers  (2020-05-18T05:49:48Z)
• Pseudo-Convolutional Policy Gradient for Sequence-to-Sequence Lip-Reading [96.48553941812366]
  Lip-reading aims to infer the speech content from the lip movement sequence. Traditional learning process of seq2seq models suffers from two problems. We propose a novel pseudo-convolutional policy gradient (PCPG) based method to address these two problems.
  arXiv  Detail & Related papers  (2020-03-09T09:12:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.