论文标题
卵石的最小化多构函数
Pebble Minimization of Polyregular Functions
论文作者
论文摘要
我们证明，当且仅当其输出大小最多线性的输入大小时，多指标的单词对字函数是常规的。此外，当且仅当其输出具有二次尺寸时，可以通过：一个带有两个卵石的传感器来实现多构函数，当它的输入中具有二次尺寸，一个带有三个卵石的换能器，并且仅当其输出的输出中的输出尺寸在其输入中等等。此外，表征是可确定的，并且给定多头函数，可以将一个带有一个transducer的数字来计算一个数字。我们将结果应用于从单词到单词的MSO解释。我们表明，MSO对k的MSO解释与K-Pebble的转换完全一致。
We show that a polyregular word-to-word function is regular if and only if its output size is at most linear in its input size. Moreover a polyregular function can be realized by: a transducer with two pebbles if and only if its output has quadratic size in its input, a transducer with three pebbles if and only if its output has cubic size in its input, etc. Moreover the characterization is decidable and, given a polyregular function, one can compute a transducer realizing it with the minimal number of pebbles. We apply the result to mso interpretations from words to words. We show that mso interpretations of dimension k exactly coincide with k-pebble transductions.
