論文の概要: Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings

• arxiv url: http://arxiv.org/abs/2604.26190v1
• Date: Wed, 29 Apr 2026 00:30:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-30 15:59:36.20773
• Title: Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings
• Title（参考訳）: Flashback: 文字列の可逆的なバイラテラルランペリング分解
• Authors: Thomas Konstantinovsky, Gur Yaari,
• Abstract要約: Flashbackは可逆的な文字列分解で、センチネルをラップした入力から最大リード文字と後続文字を繰り返す。 フラッシュバックは、文字列の最初の実行と最後の実行と、第2から最後の実行とをペアリングすることと等価です。 これにより、r の極大実行を持つ文字列に対して1+[r/2] の正確なトークンカウントが与えられ、許容される任意の二値ランペリングスキームに対して保持される下界と一致する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 我々は,最大先頭文字と後続文字をセンチネルでラップされた入力から繰り返し剥離し,各ペアを2値のトークンとして記録する可逆的文字列分解であるFlashbackを紹介する。 分解と再構成は共にO(n)時間と空間で実行される。 フラッシュバックは、文字列の最初の実行と最後の実行と、第2から最後の実行とをペアリングすることと等価です。 これにより、r の極大実行を持つ文字列に対して1+[r/2] の正確なトークンカウントが与えられ、許容される任意の二値ランペリングスキームに対して保持される下界と一致する。 既約な剥離カーネルは、少なくとも2つのシンボルを使用する; パラインドロムは正確にはラン数と対称なラン数を持つラン長符号化を持つ文字列である; 分解の像は、明示的な有限状態の特徴化を認め、一方のラン長を変更することは、正確に1つのコンテントトークンを書き換える。

関連論文リスト

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。 これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。 提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
  論文  参考訳（メタデータ） (2023-05-24T11:47:35Z)
• Reducing Discontinuous to Continuous Parsing with Pointer Network Reordering [0.7412445894287709]
  不連続木はトークンを並べ替えることで連続変種に変換することができる。 我々は与えられた入力文の連続トークン配置を正確に生成できるポインタネットワークを開発した。
  論文  参考訳（メタデータ） (2021-04-13T14:32:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。