The Target Discounted-Sum Problem
The Target Discounted-Sum Problem
复制标题
目标贴现总和问题
DOI：
10.1109/lics.2015.74
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Otop
中科院分区：
文献类型：
--
作者：
Udi Boker;T. Henzinger;J. Otop
目标折现和问题是：给定一个合理折现因子0 <；λ<;1和三个有理数a， b, t，是否存在有限或无限序列w∈{a， b}*或w∈{a， b}ω，使得Σi=0|w| w(i)λi = t？事实证明，这个问题涉及数学和计算机科学的许多领域，其可判定性问题令人惊讶地难以解决。我们解决了问题的有限版本，并展示了无限版本的难度，将其与数学和计算机科学中的各个领域和开放问题联系起来：β-展开，贴现和自动机，分段仿射映射和康托尔集的推广。我们给出了无限版本的部分结果，其中包括它对终周期序列的限制以及对于每一个n∈n λ≥1/2或λ =1/n的情况的解。我们将我们的结果用于解决贴现和自动机上的一些开放问题，其中包括有限词上不确定性自动机的精确值问题和泛函自动机的普适性和包含问题。
The target discounted-sum problem is the following: Given a rational discount factor 0 <; λ <; 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ∈ {a, b}* or w ∈ {a, b}ω, such that Σi=0|w| w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ ≥ 1/2 or λ =1/n, for every n ∈ N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata.