一句话:提出逻辑 ℒT,用 origin 函数刻画词转换的输入输出依赖,可表达所有正则函数式转换(如确定性双向传感器)。
论文关注输入到输出的有限词之间的二元关系,即词转换,并希望用逻辑刻画其性质。作者提出逻辑 ℒT,其核心是用 origin 函数把输出词的每个位置关联到它来源的输入位置,从而显式建模输入/输出依赖。ℒT 能表达不一定函数式的关系,并且可表达所有正则函数式转换,例如可由确定性双向传感器定义的那些。标题中的合成提示该逻辑还面向转换合成,但摘要未展开具体合成算法或复杂度结果。
We introduce a logic, called ℒT, to express properties of transductions, i.e. binary relations from input to output (finite) words. In ℒT, the input/output dependencies are modelled via an origin function which associates to any position of the output word, the input position from which it originates. ℒT is well-suited to express relations (which are not necessarily functional), and can express all regular functional transductions, i.e. transductions definable for instance by deterministic two-way transducers.