1id1.net
Research paper · Preprint

Token Linkages and Tree Resynchronization: An Effective Characterization

1id1:core:20261109-0001

Abstract

Recognizable Token linkages retain two original heap-preserving, constructor-fixing Token maps. Over finite ranked signatures, their behaviors are exactly the tree-automatic relations with a uniform legal leaf-tile bound and the behaviors of linear tree bimorphisms with uniformly bounded canonical cost. The latter condition is decidable from the bimorphism presentation, and a positive instance yields an effective convolution automaton, least cost bound and linkage realization. The resynchronization proof derives bounded origin geometry from endpoint tile cost; observable deletion can be eliminated, while linearity cannot simply be dropped. A direct finite-window construction gives elementary upper bounds. Further results establish canonical witnesses, an exponential deterministic-state gap after annotations are forgotten, effective closure bounds, EXPTIME-complete equivalence for explicit linkage presentations, and undecidable equivalence after yield. Position encoding and the relation to whole-sequence Transformer specifications are discussed without claiming an implemented numerical Transformer simulator.

Token SpaceTree resynchronizationTree automataDecidability

Cite this version

Wuming Pan. Token Linkages and Tree Resynchronization: An Effective Characterization. 1id1, v2, 13 November 2026. 1id1:core:20261109-0001@v2. https://1id1.net/id/core/20261109-0001/v2/

Files & integrity

FileSize
Paper PDF624 KB
LaTeX source archive76 KB
SHA-256 checksums
paper.pdf
63deb676061814029bbe07fab3e0f8aa220ad7b7a5cbaafce8b57c8288974d25
source.zip
7ec62d29a0e65e18dedb571e76071968d5b92a8cde2bdfe1808ba4b2c0de2039

Version history

v2Revised release
v1Earlier release

Release v2 replaces the current record with manuscript V10 prepared for submission to Information and Computation. Compared with v1 (V7), it includes tree resynchronization, decidable boundedness, canonical witnesses, compression and closure results, plus precise position/context motivation. Author information, availability and AI-use declarations are included. All earlier fixed releases remain unchanged.

Provenance & verification

OpenAI Codex assisted drafting, mathematical exploration, reference lookup and verification-code preparation. The author directed the work and takes responsibility for its content. This author preprint has not been represented as accepted or published by a journal.

Seven finite Python verification suites were rerun successfully on 13 November 2026. The public source archive was independently compiled to 33 pages with no LaTeX warnings. Finite checks supplement the written proofs; they do not implement the full synthesis procedure or establish general correctness by experiment.

Related paper

Counting in Token Space: Finite Witnesses, Linear Tests and Regular Heaps ↗