The target discounted-sum problem

U. Boker, T.A. Henzinger, J. Otop, in:, LICS, IEEE, 2015, pp. 750–761.

Download
OA 2015_LICS_Boker.pdf 340.21 KB

Conference Paper | Published | English

Scopus indexed
Department
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-07-01
Proceedings Title
LICS
Acknowledgement
A technical report of the article is available at: https://research-explorer.app.ist.ac.at/record/5439
Page
750 - 761
Conference
LICS: Logic in Computer Science
Conference Location
Kyoto, Japan
Conference Date
2015-007-06 – 2015-07-10
IST-REx-ID

Cite this

Boker U, Henzinger TA, Otop J. The target discounted-sum problem. In: LICS. Logic in Computer Science. IEEE; 2015:750-761. doi:10.1109/LICS.2015.74
Boker, U., Henzinger, T. A., & Otop, J. (2015). The target discounted-sum problem. In LICS (pp. 750–761). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.74
Boker, Udi, Thomas A Henzinger, and Jan Otop. “The Target Discounted-Sum Problem.” In LICS, 750–61. Logic in Computer Science. IEEE, 2015. https://doi.org/10.1109/LICS.2015.74.
U. Boker, T. A. Henzinger, and J. Otop, “The target discounted-sum problem,” in LICS, Kyoto, Japan, 2015, pp. 750–761.
Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem. LICS. LICS: Logic in Computer ScienceLogic in Computer Science 750–761.
Boker, Udi, et al. “The Target Discounted-Sum Problem.” LICS, IEEE, 2015, pp. 750–61, doi:10.1109/LICS.2015.74.
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
Access Level
OA Open Access
Date Uploaded
2020-05-15
MD5 Checksum
6abebca9c1a620e9e103a8f9222befac


Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar