论文标题
Z-聚构函数
Z-polyregular functions
论文作者
论文摘要
本文介绍了从有限词到整数的强大函数类别，我们称之为z-构规则函数。我们表明，它可以在逻辑，Z理性表达式，Z理性系列和传感器方面接受自然特征。 然后，我们研究两个子类会员问题。首先，我们表明函数的渐近生长速率是可以计算的，并且对应于使用逻辑公式表示它所需的变量数量最少。其次，我们表明z-聚调函数的一阶确定性是可以决定的。为了显示后者，我们介绍了残留换能器的原始概念，并基于基础性提供了语义表征。
This paper introduces a robust class of functions from finite words to integers that we call Z-polyregular functions. We show that it admits natural characterizations in terms of logics, Z-rational expressions, Z-rational series and transducers. We then study two subclass membership problems. First, we show that the asymptotic growth rate of a function is computable, and corresponds to the minimal number of variables required to represent it using logical formulas. Second, we show that first-order definability of Z-polyregular functions is decidable. To show the latter, we introduce an original notion of residual transducer, and provide a semantic characterization based on aperiodicity.
