---
res:
bibo_abstract:
- ' 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.
@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Udi
foaf_name: Boker, Udi
foaf_surname: Boker
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
bibo_doi: 10.2168/LMCS-10(1:10)2014
bibo_issue: '1'
bibo_volume: 10
dct_date: 2014^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/18605974
dct_language: eng
dct_publisher: International Federation of Computational Logic@
dct_title: Exact and approximate determinization of discounted-sum automata@
...