The target discounted-sum problem
published
yes
Udi
Boker
author 31E297B6-F248-11E8-B48F-1D18A9856A87
Thomas A
Henzinger
author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724
Jan
Otop
author 2FC5DA74-F248-11E8-B48F-1D18A9856A87
ToHe
department
LICS: Logic in Computer Science
Quantitative Reactive Modeling
project
Rigorous Systems Engineering
project
The Wittgenstein Prize
project
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)w, such that Σ|w| i=0 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.
IEEE2015Kyoto, Japan
eng
LICS
1043-6871 10.1109/LICS.2015.74
750 - 761
/record/5439
Boker, Udi, et al. “The Target Discounted-Sum Problem.” <i>LICS</i>, IEEE, 2015, pp. 750–61, doi:<a href="https://doi.org/10.1109/LICS.2015.74">10.1109/LICS.2015.74</a>.
U. Boker, T. A. Henzinger, and J. Otop, “The target discounted-sum problem,” in <i>LICS</i>, Kyoto, Japan, 2015, pp. 750–761.
Boker, Udi, Thomas A Henzinger, and Jan Otop. “The Target Discounted-Sum Problem.” In <i>LICS</i>, 750–61. Logic in Computer Science. IEEE, 2015. <a href="https://doi.org/10.1109/LICS.2015.74">https://doi.org/10.1109/LICS.2015.74</a>.
Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem. LICS. LICS: Logic in Computer ScienceLogic in Computer Science 750–761.
U. Boker, T.A. Henzinger, J. Otop, in:, LICS, IEEE, 2015, pp. 750–761.
Boker U, Henzinger TA, Otop J. The target discounted-sum problem. In: <i>LICS</i>. Logic in Computer Science. IEEE; 2015:750-761. doi:<a href="https://doi.org/10.1109/LICS.2015.74">10.1109/LICS.2015.74</a>
Boker, U., Henzinger, T. A., & Otop, J. (2015). The target discounted-sum problem. In <i>LICS</i> (pp. 750–761). Kyoto, Japan: IEEE. <a href="https://doi.org/10.1109/LICS.2015.74">https://doi.org/10.1109/LICS.2015.74</a>
16592018-12-11T11:53:19Z2020-01-21T13:18:24Z