一句话:研究从有限词到整数的ℤ-多正则函数,给出逻辑、表达式、级数与转换器刻画,并判定其子类成员问题。
本文研究从有限词到整数的稳健函数类——ℤ-多正则函数。作者分别用逻辑、ℤ-有理表达式、ℤ-有理级数和转换器给出自然刻画,从而统一了多种描述机制。随后考察两个子类成员判定问题:证明函数的渐近增长率可计算,且该增长率对应逻辑公式表示所需的最少变量数;并证明ℤ-多正则函数的一阶可定义性可判定。为得到后者,论文引入残差转换器这一新概念,并基于非周期性给出语义刻画。
This paper studies a robust class of functions from finite words to integers that we call ℤ-polyregular functions. We show that it admits natural characterizations in terms of logics, ℤ-rational expressions, ℤ-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 ℤ-polyregular functions is decidable. To show the latter, we introduce an original notion of residual transducer, and provide a semantic characterization based on aperiodicity.