---
res:
  bibo_abstract:
  - "Quantitative automata are nondeterministic finite automata with edge weights.
    They value a\r\nrun by some function from the sequence of visited weights to the
    reals, and value a word by its\r\nminimal/maximal run. They generalize boolean
    automata, and have gained much attention in\r\nrecent years. Unfortunately, important
    automaton classes, such as sum, discounted-sum, and\r\nlimit-average automata,
    cannot be determinized. Yet, the quantitative setting provides the potential\r\nof
    approximate determinization. We define approximate determinization with respect
    to\r\na distance function, and investigate this potential.\r\nWe show that sum
    automata cannot be determinized approximately with respect to any\r\ndistance
    function. However, restricting to nonnegative weights allows for approximate determinization\r\nwith
    respect to some distance functions.\r\nDiscounted-sum automata allow for approximate
    determinization, as the influence of a word’s\r\nsuffix is decaying. However,
    the naive approach, of unfolding the automaton computations up\r\nto a sufficient
    level, is shown to be doubly exponential in the discount factor. We provide an\r\nalternative
    construction that is singly exponential in the discount factor, in the precision,
    and\r\nin the number of states. We prove matching lower bounds, showing exponential
    dependency on\r\neach of these three parameters.\r\nAverage and limit-average
    automata are shown to prohibit approximate determinization with\r\nrespect to
    any distance function, and this is the case even for two weights, 0 and 1.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Udi
      foaf_name: Boker, Udi
      foaf_surname: Boker
      foaf_workInfoHomepage: http://www.librecat.org/personId=31E297B6-F248-11E8-B48F-1D18A9856A87
  - 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.4230/LIPIcs.FSTTCS.2012.362
  bibo_volume: 18
  dct_date: 2012^xs_gYear
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Approximate determinization of quantitative automata@
...