---
res:
bibo_abstract:
- Quantitative generalizations of classical languages, which assign to each word
a real number instead of a Boolean value, have applications in modeling resource-constrained
computation. We use weighted automata (finite automata with transition weights)
to define several natural classes of quantitative languages over finite and infinite
words; in particular, the real value of an infinite run is computed as the maximum,
limsup, liminf, limit average, or discounted sum of the transition weights. We
define the classical decision problems of automata theory (emptiness, universality,
language inclusion, and language equivalence) in the quantitative setting and
study their computational complexity. As the decidability of the language-inclusion
problem remains open for some classes of weighted automata, we introduce a notion
of quantitative simulation that is decidable and implies language inclusion. We
also give a complete characterization of the expressive power of the various classes
of weighted automata. In particular, we show that most classes of weighted automata
cannot be determinized.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Laurent
foaf_name: Doyen, Laurent
foaf_surname: Doyen
- 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.1145/1805950.1805953
bibo_issue: '4'
bibo_volume: 11
dct_date: 2010^xs_gYear
dct_language: eng
dct_publisher: ACM@
dct_title: Quantitative languages@
...