article
Exact and approximate determinization of discounted-sum automata
published
yes
Udi
Boker
author
Thomas A
Henzinger
author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724
ToHe
department
Rigorous Systems Engineering
project
Quantitative Reactive Modeling
project
A discounted-sum automaton (NDA) is a nondeterministic finite automaton with edge weights, valuing a run by the discounted sum of visited edge weights. More precisely, the weight in the i-th position of the run is divided by λi, where the discount factor λ is a fixed rational number greater than 1. The value of a word is the minimal value of the automaton runs on it. Discounted summation is a common and useful measuring scheme, especially for infinite sequences, reflecting the assumption that earlier weights are more important than later weights. Unfortunately, determinization of NDAs, which is often essential in formal verification, is, in general, not possible. We provide positive news, showing that every NDA with an integral discount factor is determinizable. We complete the picture by proving that the integers characterize exactly the discount factors that guarantee determinizability: for every nonintegral rational discount factor λ, there is a nondeterminizable λ-NDA. We also prove that the class of NDAs with integral discount factors enjoys closure under the algebraic operations min, max, addition, and subtraction, which is not the case for general NDAs nor for deterministic NDAs. For general NDAs, we look into approximate determinization, which is always possible as the influence of a word's suffix decays. We show that the naive approach, of unfolding the automaton computations up to a sufficient level, is doubly exponential in the discount factor. We provide an alternative construction for approximate determinization, which is singly exponential in the discount factor, in the precision, and in the number of states. We also prove matching lower bounds, showing that the exponential dependency on each of these three parameters cannot be avoided. All our results hold equally for automata over finite words and for automata over infinite words.
https://research-explorer.app.ist.ac.at/download/2233/4643/IST-2015-389-v1+1_1401.3957.pdf
application/pdfno
'https://creativecommons.org/licenses/by/4.0/'
International Federation of Computational Logic2014
eng
Logical Methods in Computer Science
1860597410.2168/LMCS-10(1:10)2014
101
U. Boker and T. A. Henzinger, “Exact and approximate determinization of discounted-sum automata,” <i>Logical Methods in Computer Science</i>, vol. 10, no. 1, 2014.
Boker, Udi, and Thomas A. Henzinger. “Exact and Approximate Determinization of Discounted-Sum Automata.” <i>Logical Methods in Computer Science</i>, vol. 10, no. 1, International Federation of Computational Logic, 2014, doi:<a href="https://doi.org/10.2168/LMCS-10(1:10)2014">10.2168/LMCS-10(1:10)2014</a>.
Boker, Udi, and Thomas A Henzinger. “Exact and Approximate Determinization of Discounted-Sum Automata.” <i>Logical Methods in Computer Science</i> 10, no. 1 (2014). <a href="https://doi.org/10.2168/LMCS-10(1:10)2014">https://doi.org/10.2168/LMCS-10(1:10)2014</a>.
Boker U, Henzinger TA. 2014. Exact and approximate determinization of discounted-sum automata. Logical Methods in Computer Science. 10(1).
Boker U, Henzinger TA. Exact and approximate determinization of discounted-sum automata. <i>Logical Methods in Computer Science</i>. 2014;10(1). doi:<a href="https://doi.org/10.2168/LMCS-10(1:10)2014">10.2168/LMCS-10(1:10)2014</a>
Boker, U., & Henzinger, T. A. (2014). Exact and approximate determinization of discounted-sum automata. <i>Logical Methods in Computer Science</i>, <i>10</i>(1). <a href="https://doi.org/10.2168/LMCS-10(1:10)2014">https://doi.org/10.2168/LMCS-10(1:10)2014</a>
U. Boker, T.A. Henzinger, Logical Methods in Computer Science 10 (2014).
22332018-12-11T11:56:28Z2020-01-21T13:19:25Z