---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Udi
foaf_name: Boker, Udi
foaf_surname: Boker
foaf_workInfoHomepage: http://www.librecat.org/personId=31E297B6-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
- foaf_Person:
foaf_givenName: Jan
foaf_name: Otop, Jan
foaf_surname: Otop
foaf_workInfoHomepage: http://www.librecat.org/personId=2FC5DA74-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1109/LICS.2015.74
dct_date: 2015^xs_gYear
dct_isPartOf:
- 'http://id.crossref.org/issn/1043-6871 '
dct_language: eng
dct_publisher: IEEE@
dct_title: The target discounted-sum problem@
...