The Target Discounted-Sum Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909931389583360 |
|---|---|
| author | Boker, Udi Henzinger, Thomas A. Otop, Jan |
| author_facet | Boker, Udi Henzinger, Thomas A. Otop, Jan |
| contents | 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 \in \{a,b\}^*$ or $w \in \{a,b\}^ω$, such that $\sum_{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 $λ\geq \frac{1}{2}$ or $λ=\frac{1}{n}$, for every $n\in \mathbb{N}$.
We use our results for solving some open problems on discounted-sum automata, among which are the exact-value, universality and inclusion problems for functional automata. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22979 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Target Discounted-Sum Problem Boker, Udi Henzinger, Thomas A. Otop, Jan Formal Languages and Automata Theory F.4.3; G.2.m 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 \in \{a,b\}^*$ or $w \in \{a,b\}^ω$, such that $\sum_{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 $λ\geq \frac{1}{2}$ or $λ=\frac{1}{n}$, for every $n\in \mathbb{N}$. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value, universality and inclusion problems for functional automata. |
| title | The Target Discounted-Sum Problem |
| topic | Formal Languages and Automata Theory F.4.3; G.2.m |
| url | https://arxiv.org/abs/2511.22979 |