线性递推序列中的决策问题外文翻译资料

线性递推序列中的决策问题

原作者：Joel Ouaknine and James Worrell

英国牛津大学计算机科学系

摘要：线性递推序列渗透大量数学和计算机科学内容。在本文中，我们研究线性递推序列中某些基础决策问题的研究现状，决策问题是Skolem问题（序列是否具有0？），正性的问题（序列是否总是正的？），最终正性问题（序列总是正的？）。

1. 引言

一个拥有以下属性的线性递推序列是一个无穷序列（u₀,u₁,u₂,.....）：存在常数a₁，a₂，a₃hellip;a_k，如果初始值用u₀,u₁,u₂hellip;u_k-1提供的序列，递推关系定义了其余部分唯一的序列。

线性递推序列的最有名的例子是由比萨莱昂纳多在12世纪提供：所谓的斐波那契序列0，1，1，2，3，5，8，13....，满足递推关系u_{n 2}=u_{n 1} u_n.比萨的莱昂纳多介绍了该序列应用之一，关于兔子的理想化数量增长模型。不仅斐波那契序列被进行了广泛的研究，线性递推序列形成了现在在自己的领域，成了一门广阔的学科，在数学和其他学科有众多的应用。一个深刻而广泛的对递推序列的数学方面的论述是最近的专著研究的巅峰。

在本文中，我们主要集中讨论涉及线性递推序列的决策问题。为了将这些问题明确定义，我们需要对所考虑的序列有一定的限制。首先，我们将只关注实数的序列，特别是应要求初始值以及所有的常量出现在递推关系是真实的。我们经常会专门要求进一步，例如，所有的初始值和常数是整数，或有理数，或代数数。

我们主要关心的三个的决策问题，有这样以下几种：

斯科伦问题：一个给定的线性递推序列是否具有零？

正数的问题：在一个给定的线性递推序列中全部都是正的吗？

（请注意，这个问题有两种方向，按照严格或不严格正性）

最终的正数的问题：是给定的线性递推序列全是正的，即，所有的数都是正的是否可能有数量有限的例外？

（请注意，同样地，此问题承认具有两个天然方向。）

上述问题（和密切相关的变体）在许多不同的领域具有应用，如理论生物学（L-系统的分析，种群动态），软件验证（终止线性规划的），概率模型检测（可达性马尔可夫链，随机逻辑），量子计算（量子自动阈值的问题），以及组合数学，长期改写，并生成函数的研究。例如，一个线性递推序列的特定术语通常具有组合的意义，只有当它是非负。同样，一个线性递推序列模型人口增长是生物学意义的，只有当它是均匀正数时。

在写这篇论文时，所有这些决定问题的可判定性如时间是否为整数，理性，或代数线性递推序列，是开放的，尽管部分结果是已知的。我们应尽我们所知回顾，现有技术中关于这些问题的文献，这也让我们想起了一些关于线性递推序列的关键事实。

1. 准备工作

2.1线性递推序列

我们回顾线性递推序列的一些基本性质，这些性质没有提供证据，读者请参考参考[ 4 ]详情。

是一个线性递推序列满足递推关系 我们说的序列具有k阶，a_k是非零的。（例如，因此斐波那契序列有2阶。）序列的特征多项式是：，lambda;1，hellip;，lambda;m的isin;C是P的根源的数列（可能重复）。然后使得对于所有的N有复杂的单变量多项式A₁，A₂hellip;Am，有，随后由初始值u₀,hellip;u_k-1递推序列的确该AJ的唯一值。

任何线性递推序列 k阶矩阵形式可以被定义的，在这个意义上，有一个k维方阵M，连同k维向量V和W，对所有n 它可以以M为转置矩阵序列的特征多项式的伴随矩阵，设V是序列的初始值向量（以相反的顺序），以W为载体的第一个Kminus;1值是0，kth是1。相反地，任何k维正方形矩阵M和向量V和W产生的线性递推序列 至多k阶，多亏了凯莱—汉密尔顿定理。

和 分别是为K和L线性递推序列。他们的逐点乘积 分别大多数在K和K 1的线性递增序列上。

2.2代数

众所周知，代数构成一个领域：给定两个代数，它们的总和，积，比（提供的除数为非零）又是代数。此外，如果代数是有规范的，这就表示对于这些操作可以在多项式时间内进行。决定是否两个代数相等或是代数是一个根，同样可以在多项式时间内进行的，可以决定在Z，Q，R和Rge;0的问题。例如相关的关键算法可以在[ 3 ]发现。

当讨论决策问题的代数的线性递推序列时根本的问题是算法的意义，因此我们认为相关的代数是在一些合适的有效规范的形式下提供的。

3 .Skolem问题

让我们开始有关于线性递推序列的零点最基本的结果，著名的Skolem-Mahler-Lech定理:

理论1.是一个实数的线性递推序列，它的零点集的{n：u_n=0}联合组成的有限集合F，与有限数量的算术级数A₁cup;····cup;A_l。

这个结果是由于斯科伦[15]发现，更普遍的版本随后被马勒[11，12]和瓦得到[8]。在斯科伦-马勒-莱赫定理的所有已知证据充分利用P-ADIC技术，非建设性的方式实现结果的。

3.1可判定性

[ 6 ]指出，在1930年代算法决策问题尚未获得今天一样的重要性。然而，人们习惯于把Skolem问题决定是否一个给定的线性递推序列具有一零或不具有零被作为Skolem的原始论文的发表。正如前面所提到的，这个问题是明确的，线性递推序列有必要要给予有效的形式。为此，我们应把注意力集中到整数，有理数的线性递推序列，或代数。

正如上面提到的，斯科伦 - 马勒 - 莱赫定理的证明是无效的。但是，后来Berstel和Mignotte展示了如何有效的获得所有的定理中提到的算术级数[1]。因此，临界情况下，可以归结为可能具有有限数目的零，在这种情况下，我们必须决定有限集是否为空或不是线性的复发序列。过陶哲轩认为，“[i] t是有些的离谱，这个问题仍然是开放的;这是说，这是说，我们不知道如何决定甚至“线性”自动停机问题“[17]。同样，理查德·利普顿描述这种状况为“数学尴尬”。

对斯科伦问题的可判定性部分的进展已被限制的线性递增序列的顺序来实现的。对于1和2阶的序列，民间认为判定是比较简单的。但是，判定3和4阶，不得不等待，直到20世纪80年代之前，独立地由Mignotte，Shorey，Tijdeman[13]以及Vereshchagin积极解决。

Mignotte等人和vereshchagin的证据复杂深奥。除了对ADIC技术和伽罗瓦理论，这些证明依靠在贝克的定理，阿伦·贝克由此被授予菲尔茨奖于1970年，发现于20世纪60年代末。到目前为止，所有已知的证明的Skolem问题在3和4阶都可使贝克定理的基本版本。贝克的定理和变异的极好的参考是瓦尔德施米特的书。

3.2复杂性

据我们所知，没有上限的复杂性界限在4及以下阶的Skolem问题的可判定性关系论文已发表。在[ 2 ]，布隆代尔和波特尔表明，整数线性递推序列的Skolem问题是指非确定性多项式-hard问题。我们不知道其他的下限，无论对于任意阶线性递推序列（如[ 2 ]）或序列的限制类。

在[ 10 ]中描述PSPACE-hardness在合理的情况下呈线性递推序列。不幸的是,这也是不正确的。所谓的证据试图减少非普适性关于two-letter automata的Skolem问题的。作者实际上定义了一个线性递推序列 这样，CN是所有数w的长度为n的对W的受理计算的总和。但自动机的非普适性并不清楚，意味着一个C_Nrsquo;s的必须是0。因此，这是不正确。

4积极和最终的积极性

关于积极性的问题也许是一个令人惊讶的发现，它的可判定会立即带来了斯科伦问题的可判定性。

我们知道，一个线性递推序列的逐点多又是一个线性递推序列。然而，在最坏的情况下，这一招对于k阶线性递推序列的正性问题的一个实例（阶级K2 1的线性递推序列）减少了斯科伦问题的一个实例。减少的一个直接后果是所有版本的正性问题都成为了指非确定性多项式-难度。然而，我们注意到，最终的积极性问题没有这样的减少，因此，我们知道对这个问题是没有简单的下界。

在上述减持的观点，很自然的认为，考虑正性的问题是在Skolem问题的开放讨论以后。我们已在文献中找到最早的明确的参考，但是要追溯到上世纪70年代：问题被提到的论文是（在等效制剂中）在Salomaa [ 14 ]和[ 16 ] soittola论文；在后者，笔者认为：“我们估计，Skolem问题和正性问题]将是非常困难的的问题。”

最后，我们注意到，我们讨论了斯科伦问题中的变种和减税，几乎一字不差适用于的正性和终极正问题。我们离开这些事实，给读者的一个精确的表述。

5.参考文献

[1] Berstel, J., Mignotte, M.: Deux propri′et′es d′esirables des suites r′ecurrentes

lin′eaires. Bull. Soc. Math. 104 (1976)

[2] Blondel, V.D., Portier, N.: The presence of a zero in an integer linear recurrent

sequence is NP-hard to decide. Linear Algebra and Its Applications (2002)

[3] Cohen, H.: A Course in Computational Algebraic Number Theory. Springer (1993)

[4] Everest, G., van der Poorten, A., Shparlinski, I., Ward, T.: Recurrence Sequences.

American Mathematical Society (2003)

[5] Halava, V., Harju, T., Hirvensalo, M.: Positivity of second order linear recurrent

sequences. Discrete Applied Mathematics 154(3) (2006)

[6] Halava, V., Harju, T., Hirvensalo, M., Karhumuml;aki, J.: Skolemrsquo;s problem — on

the border between decidability and undecidability. Technical Report 683, Turku

Centre for Computer Science (2005)

[7] Laohakosol, V., Tangsupphathawat, P.: Positivity of third order linear recurrence

sequences. Discrete Applied Mathematics 157(15) (2009)

[8] Lech, C.: A note on recurring series. Ark. Mat. 2 (1953)

[9] Lipton, R.J.: Mathematical embarrassments. Blog entry (December 2009),

[10] Litow, B.: A decision method for the rational sequence problem. Electronic Colloquium

on Computational Complexity (ECCC) 4(55) (1997)

[11] Mahler, K.: Eine arithmetische Eigenschaft der Taylor Koeffizienten rationaler

Funktionen. Proc. Akad. Wet. 38 (1935)

[12] Mahler, K.: On the Taylor coefficients of rational functions. Proc. Cambridge

Philos. Soc. 52 (1956)

[13] Mignotte, M., Shorey, T.N., Tijdeman, R.: The distance betw

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[286896]，资料为PDF文档或Word文档，PDF文档可免费转换为Word