Earlier Version

# The target discounted-sum problem

Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST Austria, 20p.

Download

IST-2015-335-v1+1_report.pdf
589.62 KB

*Technical Report*|

*Published*|

*English*

Department

Series Title

IST Austria Technical Report

Abstract

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.

Publishing Year

Date Published

2015-05-18

Page

20

ISSN

IST-REx-ID

### Cite this

Boker U, Henzinger TA, Otop J.

*The Target Discounted-Sum Problem*. IST Austria; 2015. doi:10.15479/AT:IST-2015-335-v1-1Boker, U., Henzinger, T. A., & Otop, J. (2015).

*The target discounted-sum problem*. IST Austria. https://doi.org/10.15479/AT:IST-2015-335-v1-1Boker, Udi, Thomas A Henzinger, and Jan Otop.

*The Target Discounted-Sum Problem*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-335-v1-1.U. Boker, T. A. Henzinger, and J. Otop,

*The target discounted-sum problem*. IST Austria, 2015.Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST Austria, 20p.

Boker, Udi, et al.

*The Target Discounted-Sum Problem*. IST Austria, 2015, doi:10.15479/AT:IST-2015-335-v1-1.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Main File(s)**

File Name

IST-2015-335-v1+1_report.pdf
589.62 KB

Access Level

Open Access

Date Uploaded

2018-12-12

MD5 Checksum

40405907aa012acece1bc26cf0be554d