一句话：polyregular 函数输出规模 O(n^k) 当且仅当可由 k 维 MSO 解释定义，且 pebble transducer 无此刻画。
本文研究 polyregular 函数，即输出长度为输入长度多项式级的字符串到字符串函数。作者证明，一个 polyregular 函数的输出规模为 O(n^k)，当且仅当它可由 k 维 MSO 解释定义：输出每个位置由一元二阶逻辑在输入位置的 k 元组上解释得到。该结果给出输出增长率的逻辑刻画。作者进一步证明该刻画不能推广到 pebble transducer：对每个 k，都存在输出规模为二次的 polyregular 函数，其计算至少需要 k 个 pebble，从而分离了两类模型的表达与资源需求。
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 ∈ 1, 2, …} there is a polyregular function of quadratic output size which needs at least k pebbles to be computed.