流式字符串转导器

SST 像一位只读一遍输入、同时维护若干可伸长文本片段的编辑者。更新只能连接常量和已有片段，不能检查寄存器内部字符、按长度分支或删除中间某一位；有限控制负责所有条件判断。

同步赋值是模型的核心。如果写 $X:=XY,Y:=X$，新 $Y$ 取得的是旧 $X$，而不是已经更新后的 $XY$。把它当顺序程序执行会在第二个赋值中重复 $Y$，从第一步起便定义了另一个函数。

例如更新前 $X=\mathtt{\text{ab}}$、$Y=\mathtt{\text{c}}$，同步执行 $X:=XY,Y:=X$ 后应得到 $X=\mathtt{\text{abc}}$、$Y=\mathtt{\text{ab}}$。若误按从左到右赋值，第二句会读到新 $X$，错误地得到 $Y=\mathtt{\text{abc}}$。这一小例足以作为实现同步语义的单步测试。

输出通常延迟到输入结束，由一个表达式规定片段顺序。这不等于机器把任意操作留到最后：扫描过程中每个更新已经不可逆地构造寄存器表达式，终态只做一次有限拼接。

取单寄存器 $X$，初值 $\epsilon$，对当前输入字符 $a$ 执行 copyful 更新

输入 abc 时，寄存器依次为

若终态表达式为 $X$，输出就是 aabaabc。长度递推 $L_{n+1}=2L_n+1$、$L_0=0$ 给出 $L_n=2^n-1$；指数增长不是实现偶然，而是旧 $X$ 在右式出现两次造成的复制。

这个例子也是一般 SST 与 copyless SST 的明确分界。有限字母表上的固定 copyless SST 输出长度至多是输入长度的常数倍加常数，因而不可能实现上述族。反过来，寄存器虽可无限增长，SST 仍不能根据“$X$ 是否等于某个先前片段”分支，因为转移函数看不到 $X$ 的内容。

部分性由缺失输入转移或未定义终态表达式给出。若输入读完但 $F(q)$ 未定义，不能把所有寄存器自动连接；寄存器的次序和是否输出必须由 $F$ 明写。空输入同理，只代入初值并检查 $F(q_0)$。

一般 copyful SST 能以很小控制图描述指数输出，因此表达力超过 regular string functions。其代数语义可看作由输入驱动的一串字符串代换；这也使等价问题与 HDT0L 序列等价等深层判定问题相连，而不是普通 DFA 等价的状态对搜索。

字符串寄存器适合构造嵌套转义、字段重排和多份派生视图。实现时可用 rope 或表达式 DAG 延迟物化，避免每轮真实复制长字符串；但 DAG 共享只是运行优化，不会把 copyful 语义变成 copyless。

若任务需要正则、线性大小的字符串变换，copyless 流式字符串转导器公理库Copyless 流式字符串转导器Copyless streaming string transducer · Copyless SST每轮同步更新中每个旧寄存器至多被使用一次，从而禁止复制已累积字符串的 SST 子类。提供更稳健的限制，并恰好对应确定双向转导器。若确实需要指数展开，则应明确接受输出本身已占指数空间，任何实现都无法用次线性于输出长度的时间打印结果。

寄存器更新也可视为对表达式 DAG 的代换。求值器可以一直保留节点共享，到终态再展开输出；若某个旧节点被 copyful 更新引用两次，共享 DAG 仍很小，但最终打印会遍历它两次。表示压缩与语义输出长度必须分开报告。