论文标题
卵石最小化：最后一个定理
Pebble minimization: the last theorems
论文作者
论文摘要
卵石换能器是嵌套的双向传感器，可以在其输入词上丢下标记（称为“鹅卵石”）。这样的机器可以计算其输出大小在其输入大小的多项式的功能。它们可以看作是简单的递归程序，其递归高度是有限的。一个自然的问题是给定卵石换能器，以计算具有最小递归高度的等效卵石换能器。自引入模型以来，这个问题就开放了。 在本文中，我们研究了卵石换能器的两个限制，这些限制无法看到标记（Nguyên等人引入的“盲卵石传感器”），或者只能看到最后一个标记掉落（“由Engelfriet等人引入的最后一个卵石传感器”）。对于这两种模型，我们都提供了一种有效的算法来最大程度地减少递归高度。两种情况下使用的关键属性是，其输出大小是线性的函数（分别二次，立方等）始终可以由递归高度为1（2、3等）的机器计算。我们最终表明，一旦考虑可以看到多个标记的机器，该关键属性就会失败。
Pebble transducers are nested two-way transducers which can drop marks (named "pebbles") on their input word. Such machines can compute functions whose output size is polynomial in the size of their input. They can be seen as simple recursive programs whose recursion height is bounded. A natural problem is, given a pebble transducer, to compute an equivalent pebble transducer with minimal recursion height. This problem is open since the introduction of the model. In this paper, we study two restrictions of pebble transducers, that cannot see the marks ("blind pebble transducers" introduced by Nguyên et al.), or that can only see the last mark dropped ("last pebble transducers" introduced by Engelfriet et al.). For both models, we provide an effective algorithm for minimizing the recursion height. The key property used in both cases is that a function whose output size is linear (resp. quadratic, cubic, etc.) can always be computed by a machine whose recursion height is 1 (resp. 2, 3, etc.). We finally show that this key property fails as soon as we consider machines that can see more than one mark.
