一句话：提出转换器的轮次模拟与轮次等价，并判定给定 k 及存在 k 时的模拟问题。
本文研究字母到字母转换器之间的近似行为关系。作者将输入词划分为长度固定为 k 的连续子词，称为轮次，并定义：T1 被 T2 k-轮次模拟，即对任意输入词 x，可在每轮内置换字母，使 T2 在置换后词上的输出是 T1 在 x 上输出的一个置换；两转换器互相模拟则为 k-轮次等价。论文解决两个判定问题：当 k 给定为输入时，T2 是否 k-轮次模拟 T1；以及是否存在某个 k 使二者具有该关系。最后，作者将定义应用于多进程系统的进程对称性，说明 k-轮次等价对应于对进程身份置换的稳定性。
Letter-to-letter transducers are a standard formalism for modeling reactive systems. Often, two transducers that model similar systems differ locally from one another, by behaving similarly, up to permutations of the input and output letters within "rounds". In this work, we introduce and study notions of simulation by rounds and equivalence by rounds of transducers. In our setting, words are partitioned to consecutive subwords of a fixed length $k$, called rounds. Then, a transducer $\mathcal{T}_1$ is $k$-round simulated by transducer $\mathcal{T}_2$ if, intuitively, for every input word $x$, we can permute the letters within each round in $x$, such that the output of $\mathcal{T}_2$ on the permuted word is itself a permutation of the output of $\mathcal{T}_1$ on $x$. Finally, two transducers are $k$-round equivalent if they simulate each other. We solve two main decision problems, namely whether $\mathcal{T}_2$ $k$-round simulates $\mathcal{T}_1$ (1) when $k$ is given as input, and (2) for an existentially quantified $k$. We demonstrate the usefulness of the definitions by applying them to process symmetry: a setting in which a permutation in the identities of processes in a multi-process system naturally gives rise to two transducers, whose $k$-round equivalence corresponds to stability against such permutations.
@article{paperbot2175,
title = {Simulation by Rounds of Letter-to-Letter Transducers},
author = {Antonio Abu Nassar and Shaull Almagor},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 4},
year = {2023},
doi = {10.46298/lmcs-19(4:19)2023}
}