Determinizing discounted-sum automata

Boker U, Henzinger TA. 2011. Determinizing discounted-sum automata. CSL: Computer Science Logic, LIPIcs, vol. 12, 82–96.

Download
OA IST-2012-82-v1+1_Determinizing_discounted-sum_automata.pdf 504.27 KB [Published Version]

Conference Paper | Published | English

Scopus indexed
Series Title
LIPIcs
Abstract
A discounted-sum automaton (NDA) is a nondeterministic finite automaton with edge weights, which values 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 lambda^i, where the discount factor lambda is a fixed rational number greater than 1. Discounted summation is a common and useful measuring scheme, especially for infinite sequences, which reflects the assumption that earlier weights are more important than later weights. Determinizing automata is often essential, for example, in formal verification, where there are polynomial algorithms for comparing two deterministic NDAs, while the equivalence problem for NDAs is not known to be decidable. Unfortunately, however, discounted-sum automata are, in general, not determinizable: it is currently known that for every rational discount factor 1 < lambda < 2, there is an NDA with lambda (denoted lambda-NDA) that cannot be determinized. We provide positive news, showing that every NDA with an integral factor is determinizable. We also complete the picture by proving that the integers characterize exactly the discount factors that guarantee determinizability: we show that for every non-integral rational factor lambda, there is a nondeterminizable lambda-NDA. Finally, we 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. This shows that for integral discount factors, the class of NDAs forms an attractive specification formalism in quantitative formal verification. All our results hold equally for automata over finite words and for automata over infinite words.
Publishing Year
Date Published
2011-08-31
Publisher
Springer
Volume
12
Page
82 - 96
Conference
CSL: Computer Science Logic
Conference Location
Bergen, Norway
Conference Date
2011-09-12 – 2011-09-15
IST-REx-ID

Cite this

Boker U, Henzinger TA. Determinizing discounted-sum automata. In: Vol 12. Springer; 2011:82-96. doi:10.4230/LIPIcs.CSL.2011.82
Boker, U., & Henzinger, T. A. (2011). Determinizing discounted-sum automata (Vol. 12, pp. 82–96). Presented at the CSL: Computer Science Logic, Bergen, Norway: Springer. https://doi.org/10.4230/LIPIcs.CSL.2011.82
Boker, Udi, and Thomas A Henzinger. “Determinizing Discounted-Sum Automata,” 12:82–96. Springer, 2011. https://doi.org/10.4230/LIPIcs.CSL.2011.82.
U. Boker and T. A. Henzinger, “Determinizing discounted-sum automata,” presented at the CSL: Computer Science Logic, Bergen, Norway, 2011, vol. 12, pp. 82–96.
Boker U, Henzinger TA. 2011. Determinizing discounted-sum automata. CSL: Computer Science Logic, LIPIcs, vol. 12, 82–96.
Boker, Udi, and Thomas A. Henzinger. Determinizing Discounted-Sum Automata. Vol. 12, Springer, 2011, pp. 82–96, doi:10.4230/LIPIcs.CSL.2011.82.
All files available under the following license(s):
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
250603c6be8ccad4fbd4d7b24221f0ee


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar