Approximate determinization of quantitative automata

U. Boker, T.A. Henzinger, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 362–373.

Download
OA 559.07 KB

Conference Paper | Published | English
Department
Series Title
LIPIcs
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, discounted-sum, and limit-average 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. Discounted-sum 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 limit-average 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.
Publishing Year
Date Published
2012-12-01
Proceedings Title
Leibniz International Proceedings in Informatics
Acknowledgement
We thank Laurent Doyen for great ideas and valuable help in analyzing discounted-sum automata.
Volume
18
Page
362 - 373
Conference
FSTTCS: Foundations of Software Technology and Theoretical Computer Science
Conference Location
Hyderabad, India
Conference Date
2012-12-15 – 2012-12-17
IST-REx-ID

Cite this

Boker U, Henzinger TA. Approximate determinization of quantitative automata. In: Leibniz International Proceedings in Informatics. Vol 18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:362-373. doi:10.4230/LIPIcs.FSTTCS.2012.362
Boker, U., & Henzinger, T. A. (2012). Approximate determinization of quantitative automata. In Leibniz International Proceedings in Informatics (Vol. 18, pp. 362–373). Hyderabad, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.362
Boker, Udi, and Thomas A Henzinger. “Approximate Determinization of Quantitative Automata.” In Leibniz International Proceedings in Informatics, 18:362–73. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.362.
U. Boker and T. A. Henzinger, “Approximate determinization of quantitative automata,” in Leibniz International Proceedings in Informatics, Hyderabad, India, 2012, vol. 18, pp. 362–373.
Boker U, Henzinger TA. 2012. Approximate determinization of quantitative automata. Leibniz International Proceedings in Informatics. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 18. 362–373.
Boker, Udi, and Thomas A. Henzinger. “Approximate Determinization of Quantitative Automata.” Leibniz International Proceedings in Informatics, vol. 18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 362–73, doi:10.4230/LIPIcs.FSTTCS.2012.362.
All files available under the following license(s):
Creative Commons License:
CC-BY-NC-NDCreative Commons Attribution-NonCommercial-NoDerivs (CC BY-NC-ND 4.0)
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:10:37Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar