Abstract
Quantitative automata are nondeterministic finite automata with edge weights. They value a run by some function from the sequence of visited weights to the reals, and value a word by its minimal/maximal run. They generalize boolean automata, and have gained much attention in recent years. Unfortunately, important automaton classes, such as sum, discountedsum, and limitaverage automata, cannot be determinized. Yet, the quantitative setting provides the potential of approximate determinization. We define approximate determinization with respect to a distance function, and investigate this potential.
We show that sum automata cannot be determinized approximately with respect to any distance function. However, restricting to nonnegative weights allows for approximate determinization with respect to some distance functions.
Discountedsum automata allow for approximate determinization, as the influence of a word's suffix is decaying. However, the naive approach, of unfolding the automaton computations up to a sufficient level, is shown to be doubly exponential in the discount factor. We provide an alternative construction that is singly exponential in the discount factor, in the precision, and in the number of states. We prove matching lower bounds, showing exponential dependency on each of these three parameters.
Average and limitaverage automata are shown to prohibit approximate determinization with respect to any distance function, and this is the case even for two weights, 0 and 1.
BibTeX  Entry
@InProceedings{boker_et_al:LIPIcs:2012:3873,
author = {Udi Boker and Thomas A. Henzinger},
title = {{Approximate Determinization of Quantitative Automata}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {362373},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897477},
ISSN = {18688969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3873},
URN = {urn:nbn:de:0030drops38739},
doi = {10.4230/LIPIcs.FSTTCS.2012.362},
annote = {Keywords: Quantitative; Automata; Determinization; Approximation}
}
Keywords: 

Quantitative; Automata; Determinization; Approximation 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) 
Issue Date: 

2012 
Date of publication: 

10.12.2012 