We consider polyregular functions, which are certain string-to-string functions that have polynomial output size. We prove that a polyregular function has output size $\mathcal O(n^k)$ if and only if it can be defined by an MSO interpretation of dimension $k$, i.e. a string-to-string transformation where every output position is interpreted, using monadic second-order logic MSO, in some $k$-tuple of input positions. We also show that this characterization does not extend to pebble transducers, another model for describing polyregular functions: we show that for every $k \in \{1,2,\ldots\}$ there is a polyregular function of quadratic output size which needs at least $k$ pebbles to be computed.


翻译:我们考虑多规则函数,这些函数是具有多项式输出大小的某些字符串到字符串的函数。我们证明,对于多规则函数,如果它可以由一个维数为$k$的MSO解释来定义,则其输出大小为$\mathcal O(n^k)$,即,一个字符串到字符串的转换,其中每个输出位置都是在一些$k$个输入位置上使用单调二阶逻辑MSO解释的。我们还表明,这种表征不适用于卵石传感器,另一种描述多规则函数的模型:我们展示对于每个$k∈{1,2,…}$,存在一个二次输出大小的多规则函数,它至少需要$k$个卵石才能计算出来。

0
下载
关闭预览

相关内容

专知会员服务
27+阅读 · 2021年5月2日
专知会员服务
76+阅读 · 2021年3月16日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
因果效应估计组合拳:Reweighting和Representation
PaperWeekly
0+阅读 · 2022年9月2日
深度卷积神经网络中的降采样
极市平台
12+阅读 · 2019年5月24日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年6月7日
Arxiv
0+阅读 · 2023年6月7日
Arxiv
0+阅读 · 2023年6月7日
Arxiv
0+阅读 · 2023年6月4日
Arxiv
0+阅读 · 2023年6月3日
VIP会员
相关VIP内容
专知会员服务
27+阅读 · 2021年5月2日
专知会员服务
76+阅读 · 2021年3月16日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
相关基金
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员