@inproceedings{10.1145_3661814.3662090,
    author = {Boker, Udi},
    title = {Discounted-Sum Automata with Real-Valued Discount Factors},
    year = {2024},
    isbn = {9798400706608},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    url = {https://doi.org/10.1145/3661814.3662090},
    doi = {10.1145/3661814.3662090},
    abstract = {A nondeterministic discounted-sum automaton (NDA) values a run by the discounted sum of the visited transition weights. That is, the weight in the i-th position of a run of a {$\lambda$}-NDA is divided by {$\lambda$}i, for a fixed discount factor {$\lambda$} > 1. This allows to model systems in which the influence of current events is more significant than that of future ones, a key paradigm in economics and other disciplines.NDAs were considered so far with respect to a rational discount factor {$\lambda$}. It is known that for every integer {$\lambda$} > 1, the class of {$\lambda$}-NDAs has good computational properties: it is closed under determinization and under the algebraic operations min, max, addition, and subtraction, and there are algorithms for the classic decision problems, such as equivalence and containment, on its automata. On the other hand, for every rational {$\lambda$} ϵ Q  N, the class of {$\lambda$}-NDAs lacks these closure properties, and it is open whether the classic decision problems on it are decidable. This situation significantly limits the usage of NDAs, as integral discount factors enforce at least a double decay in each step of the computation, and only allow for a very coarse decay granularity.We study NDAs with real discount factors, and show that for every Pisot number {$\lambda$}, the class of {$\lambda$}-NDAs retains all of the above good computational properties of integral NDAs. Furthermore, as is the case with integral discount factors, we show that it is also decidable to compare two NDAs with different Pisot discount factors. To this end, we generalize known results on the representation of numbers in Pisot base, and connect them to NDAs. Complementing our positive results, we show that if a class of {$\lambda$}-NDAs is closed under determinization or under algebraic operations, then the discount factor {$\lambda$} must be a Pisot number and the transition weights must be in Q({$\lambda$}). All our results hold equally for automata on finite words and for automata on infinite words.},
    booktitle = {Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science},
    articleno = {15},
    numpages = {14},
    keywords = {automata, discounted-sum, quantitative verification, Pisot numbers, beta expansion},
    location = {Tallinn, Estonia},
    series = {LICS '24},
    date-added = {2024-7-15 6:8:7 +0100}
}

@inproceedings{10.1145_3661814.3662090, author = {Boker, Udi}, title = {Discounted-Sum Automata with Real-Valued Discount Factors}, year = {2024}, isbn = {9798400706608}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3661814.3662090}, doi = {10.1145/3661814.3662090}, abstract = {A nondeterministic discounted-sum automaton (NDA) values a run by the discounted sum of the visited transition weights. That is, the weight in the i-th position of a run of a {$\lambda$}-NDA is divided by {$\lambda$}i, for a fixed discount factor {$\lambda$} > 1. This allows to model systems in which the influence of current events is more significant than that of future ones, a key paradigm in economics and other disciplines.NDAs were considered so far with respect to a rational discount factor {$\lambda$}. It is known that for every integer {$\lambda$} > 1, the class of {$\lambda$}-NDAs has good computational properties: it is closed under determinization and under the algebraic operations min, max, addition, and subtraction, and there are algorithms for the classic decision problems, such as equivalence and containment, on its automata. On the other hand, for every rational {$\lambda$} ϵ Q N, the class of {$\lambda$}-NDAs lacks these closure properties, and it is open whether the classic decision problems on it are decidable. This situation significantly limits the usage of NDAs, as integral discount factors enforce at least a double decay in each step of the computation, and only allow for a very coarse decay granularity.We study NDAs with real discount factors, and show that for every Pisot number {$\lambda$}, the class of {$\lambda$}-NDAs retains all of the above good computational properties of integral NDAs. Furthermore, as is the case with integral discount factors, we show that it is also decidable to compare two NDAs with different Pisot discount factors. To this end, we generalize known results on the representation of numbers in Pisot base, and connect them to NDAs. Complementing our positive results, we show that if a class of {$\lambda$}-NDAs is closed under determinization or under algebraic operations, then the discount factor {$\lambda$} must be a Pisot number and the transition weights must be in Q({$\lambda$}). All our results hold equally for automata on finite words and for automata on infinite words.}, booktitle = {Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science}, articleno = {15}, numpages = {14}, keywords = {automata, discounted-sum, quantitative verification, Pisot numbers, beta expansion}, location = {Tallinn, Estonia}, series = {LICS '24}, date-added = {2024-7-15 6:8:7 +0100} }