一句话：将块积运算融入可数词正则语言的代数框架，并用迭代块积刻画一阶逻辑与线性时序逻辑片段。
论文研究可数词上正则语言的代数理论，目标是把有限词情形中有效的块积运算无缝推广到可数词框架。作者在近期发展的可数词代数框架中引入块积，并证明了一个简单但精细的块积原则。基于此，他们用强迭代与弱迭代块积分别刻画一阶逻辑和仅含两个变量的一阶逻辑，从而得到 Schützenberger–McNaughton–Papert 定理在可数词上的完整类似物。论文还通过给出一个自然片段的代数刻画，阐明块积在线性时序逻辑中的作用。
We propose a seamless integration of the block product operation to the recently developed algebraic framework for regular languages of countable words. A simple but subtle accompanying block product principle has been established. Building on this, we generalize the well-known algebraic characterizations of first-order logic (resp. first-order logic with two variables) in terms of strongly (resp. weakly) iterated block products. We use this to arrive at a complete analogue of Schiitzenberger-McNaughton-Papert theorem for countable words. We also explicate the role of block products for linear temporal logic by formulating a novel algebraic characterization of a natural fragment.
DOI 原文 ·
@inproceedings{paperbot5022,
title = {Block products for algebras over countable words and applications to logic},
author = {Bharat Adsul and Saptarshi Sarkar and A. V. Sreejith},
booktitle = {LICS},
year = {2019},
doi = {10.1109/lics.2019.8785669}
}