paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Logics for Word Transductions with Synthesis

词转换及其合成的逻辑
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 2/10 · 论文属于逻辑与自动机、词转换与合成理论,虽涉及形式化方法和合成,但与用户核心关注的 ML/Agent 程序静态分析、LLM 与静态分析/形式化验证交叉、浮点程序分析或贝叶斯程序分析均无直接关联。引用 5 inbox
Luc Dartois, Emmanuel Filiot, Nathan Lhote
crossref: 2026-09-12

AI 速览

一句话:提出逻辑 ℒT,用 origin 函数刻画词转换的输入输出依赖,可表达所有正则函数式转换(如确定性双向传感器)。

论文关注输入到输出的有限词之间的二元关系,即词转换,并希望用逻辑刻画其性质。作者提出逻辑 ℒT,其核心是用 origin 函数把输出词的每个位置关联到它来源的输入位置,从而显式建模输入/输出依赖。ℒT 能表达不一定函数式的关系,并且可表达所有正则函数式转换,例如可由确定性双向传感器定义的那些。标题中的合成提示该逻辑还面向转换合成,但摘要未展开具体合成算法或复杂度结果。

问题
如何为输入/输出有限词之间的二元关系(词转换)提供逻辑刻画,并沿标题所指方向支持合成。
方法
引入逻辑 ℒT,通过 origin 函数将输出位置映射到来源输入位置,以逻辑公式描述转换关系。
评估
理论表达能力分析:ℒT 可表达不一定函数式的关系,且可表达所有正则函数式转换,例如确定性双向传感器可定义者;摘要未给出实验评估。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot4324,
  title = {Logics for Word Transductions with Synthesis},
  author = {Luc Dartois and Emmanuel Filiot and Nathan Lhote},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209181}
}