1id1.net
Research paper · Preprint

Token Linkages: Effective Realizability and Decision Boundaries

1id1:core:20261109-0001@v1

Abstract

Token linkages use structural witnesses and two original heap-preserving tree Token maps. For finite ranked signatures, their recognizable behaviors admit an effective characterization: a convolution-recognizable relation is realizable exactly when it has no root core obstruction and its language of canonically forced leaf tiles is finite. A four-state annotation of the relation automaton constructs this language. With fixed maximum rank, realizability and the least uniform tile-size bound are computable in polynomial time; constructing a full realization need not have polynomial output size. The canonical decomposition requires a core check before descending through matching constructors. We retain recognizable pullback composition, EXPTIME-complete equivalence of explicit linkage presentations, and undecidable equivalence after yield. Context can be internalized, while weighted behavior records witness multiplicity. Comparisons with established tree-relation classes locate the constructor-fixing fragment without claiming a new general transducer formalism. Node-size bounds permit shorter tree outputs but limit unbounded contraction in a fixed finite presentation.

Token SpaceTree automataTree relationsDecidability

Cite this version

Wuming Pan. Token Linkages: Effective Realizability and Decision Boundaries. 1id1, v1, 9 November 2026. 1id1:core:20261109-0001@v1. https://1id1.net/id/core/20261109-0001/v1/

Files & integrity

FileSize
Paper PDF507 KB
LaTeX source archive40 KB
SHA-256 checksums
paper.pdf
f1869a2a902827dc5a7461c117104265a5581dfd1d16c4f972e9ab53e5f0be1b
source.zip
0dc3ffc4612aba70b38404ab7522081d37c972c3718fcd80a38d45d6081f3d11

Version history

v1Initial deposit

Initial public release of manuscript V7. Repository imprint and public-version references have been added; mathematical statements, proofs and recorded verification results are unchanged.

Provenance & verification

AI-assisted preparation of the publication copy and source archive. The author remains responsible for the content. This deposit does not assert completed peer review.

The source archive contains five finite verification programs and recorded passing results. The effective-cut checks include 6,400 tree-pair comparisons and exact finite and infinite automaton cases. Bounded checks supplement the proofs; they do not establish general complexity or undecidability.

Related paper

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