一句话：定义带多个整数折扣因子的非确定折扣和自动机，揭示其不可判定性，并提出整洁子类恢复良好性质。
折扣和自动机用折扣因子弱化未来事件的影响，但既有非确定折扣和自动机（NDA）仅考虑单一折扣因子：单一整数因子时具有确定化封闭、对 min/max/加/减封闭以及等价与包含可判定等良好性质，任意有理因子则丢失这些性质。本文定义每条转移可有不同整数折扣因子的非确定多折扣和自动机（integral NMDA），证明一般情形下其不确定化封闭、代数运算不封闭且包含问题不可判定。随后提出 tidy NMDA，其折扣因子选择取决于已读词前缀，涵盖折扣因子关联动作或经过时间的特例。作者证明对任意选择函数 θ，θ-NMDA 保持单一整数因子 NDA 的良好性质与判定复杂度，且 tidy NMDA 与任意选择折扣因子的确定型整数 NMDA 表达力相同。
Discounting the influence of future events is a key paradigm in economics and it is widely used in computer-science models, such as games, Markov decision processes (MDPs), reinforcement learning, and automata. While a single game or MDP may allow for several different discount factors, nondeterministic discounted-sum automata (NDAs) were only studied with respect to a single discount factor. It is known that every class of NDAs with an integer as the discount factor has good computational properties: It is closed under determinization and under the algebraic operations min, max, addition, and subtraction, and there are algorithms for its basic decision problems, such as automata equivalence and containment. Extending the integer discount factor to an arbitrary rational number, loses most of these good properties. We define and analyze nondeterministic discounted-sum automata in which each transition can have a different integral discount factor (integral NMDAs). We show that integral NMDAs with an arbitrary choice of discount factors are not closed under determinization and under algebraic operations and that their containment problem is undecidable. We then define and analyze a restricted class of integral NMDAs, which we call tidy NMDAs, in which the choice of discount factors depends on the prefix of the word read so far. Among their special cases are NMDAs that correlate discount factors to actions (alphabet letters) or to the elapsed time. We show that for every function $\theta$ that defines the choice of discount factors, the class of $\theta$-NMDAs enjoys all of the above good properties of NDAs with a single integral discount factor, as well as the same complexity of the required decision problems. Tidy NMDAs are also as expressive as deterministic integral NMDAs with an arbitrary choice of discount factors.Comment: arXiv admin note: text overlap with arXiv:2301.04086
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2307-08780,
title = {Discounted-Sum Automata with Multiple Discount Factors},
author = {Udi Boker and Guy Hefetz},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 2},
year = {2025},
doi = {10.46298/lmcs-21(2:18)2025}
}