Sequences of numbers (either natural integers, or integers or rational) of level $k \in \mathbb{N}$ have been defined in \cite{Fra05,Fra-Sen06} as the sequences which can be computed by deterministic pushdown automata of level $k$. This definition has been extended to sequences of {\em words} indexed by {\em words} in \cite{Sen07,Fer-Mar-Sen14}. We characterise here the sequences of level 3 as the compositions of two HDT0L-systems. Two applications are derived: - the sequences of rational numbers of level 3 are characterised by polynomial recurrences - the equality problem for sequences of rational numbers of level 3 is decidable.
翻译:在\ cite{ Fra05, Fra- Sen06} 中定义了美元水平的数值序列(自然整数或整数或合理数) 。 在\ cite{ sen07, Fer- Mar- Sen14} 中,该定义被扩展至 {em 单词索引的 {em 单词的序列 。 我们在此将第 3 级的序列定性为两个 HDT0L 系统的构成。 有两个应用来源 : - 第 3 级的理性数序列以多数值复现为特征 - 第 3 级 理性数序列的平等问题可以解密 。