We show a theorem on monadic second-order k-ary queries on finite words. It may be illustrated by the following example: if the number of results of a query on binary strings is O(number of 0s $\times$ number of 1s), then each result can be MSO-definably identified from a 0-position, a 1-position and some finite data. Our proofs also handle the case of first-order logic / aperiodic monoids. Thus we can state and prove the folklore theorem that dimension minimisation holds for first-order string-to-string interpretations.
翻译：我们提出了一个关于有限单词上的一元二阶k元查询的定理。该定理可通过以下示例说明：若二进制字符串上某个查询的结果数量为O(0的数量 × 1的数量)，则每个结果均可通过MSO可定义的方式从一个0位置、一个1位置及某些有限数据中识别。我们的证明方法同样适用于一阶逻辑/非周期幺半群的情形。因此，我们可以陈述并证明一个广为流传的定理：对于一阶字符串到字符串的解释，维度最小化性质成立。
相关内容
Arxiv
0+阅读 · 2025年12月29日
Arxiv
0+阅读 · 2025年12月28日
Arxiv
0+阅读 · 2025年12月26日
相关VIP内容
相关资讯
微信扫码咨询专知VIP会员