论文标题
关于多构函数的增长率
On the growth rate of polyregular functions
论文作者
论文摘要
我们考虑多向函数，它们是具有多项式输出大小的某些字符串函数。我们证明，当时多构函数具有输出尺寸$ \ MATHCAL O（n^k）$，并且仅当它可以通过MSO解释dimension $ k $的MSO解释来定义，即使用Monadic的二阶逻辑MSO解释每个输出位置，在某些$ k $ -k $ - toples中，将每个输出位置解释为输入位置。我们还表明，这种表征不会扩展到卵石换能器，这是描述多指标函数的另一个模型：我们证明，对于每一个$ k \ in \ {1,2，\ ldots \} $，都有一个二次输出大小的多型函数，它至少需要计算$ k $ pebbles。
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.
