---
_id: '4540'
abstract:
- lang: eng
text: Weighted automata are nondeterministic automata with numerical weights on
transitions. They can define quantitative languages L that assign to each word
w a real number L(w). In the case of infinite words, the value of a run is naturally
computed as the maximum, limsup, liminf, limit average, or discounted sum of the
transition weights. We study expressiveness and closure questions about these
quantitative languages. We first show that the set of words with value greater
than a threshold can be non-w-regular for deterministic limit-average and discounted-sum
automata, while this set is always w-regular when the threshold is isolated (i.e.,
some neighborhood around the threshold contains no word). In the latter case,
we prove that the w-regular language is robust against small perturbations of
the transition weights. We next consider automata with transition weights 0 or
1 and show that they are as expressive as general weighted automata in the limit-average
case, but not in the discounted-sum case. Third, for quantitative languages L-1
and L-2, we consider the operations max(L-1, L-2), min(L-1, L-2), and 1-L-1, which
generalize the boolean operations on languages, as well as the sum L-1 + L-2.
We establish the closure properties of all classes of quantitative languages with
respect to these four operations.
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Doyen L, Henzinger TA. Expressiveness and closure properties
for quantitative languages. In: IEEE; 2009:199-208. doi:10.1109/LICS.2009.16'
apa: 'Chatterjee, K., Doyen, L., & Henzinger, T. A. (2009). Expressiveness and
closure properties for quantitative languages (pp. 199–208). Presented at the
LICS: Logic in Computer Science, IEEE. https://doi.org/10.1109/LICS.2009.16'
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Expressiveness
and Closure Properties for Quantitative Languages,” 199–208. IEEE, 2009. https://doi.org/10.1109/LICS.2009.16.
ieee: 'K. Chatterjee, L. Doyen, and T. A. Henzinger, “Expressiveness and closure
properties for quantitative languages,” presented at the LICS: Logic in Computer
Science, 2009, pp. 199–208.'
ista: 'Chatterjee K, Doyen L, Henzinger TA. 2009. Expressiveness and closure properties
for quantitative languages. LICS: Logic in Computer Science, 199–208.'
mla: Chatterjee, Krishnendu, et al. Expressiveness and Closure Properties for
Quantitative Languages. IEEE, 2009, pp. 199–208, doi:10.1109/LICS.2009.16.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, in:, IEEE, 2009, pp. 199–208.
conference:
name: 'LICS: Logic in Computer Science'
date_created: 2018-12-11T12:09:23Z
date_published: 2009-01-01T00:00:00Z
date_updated: 2023-02-23T11:46:11Z
day: '01'
doi: 10.1109/LICS.2009.16
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 199 - 208
publication_status: published
publisher: IEEE
publist_id: '181'
pubrep_id: '55'
quality_controlled: '1'
related_material:
record:
- id: '3867'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Expressiveness and closure properties for quantitative languages
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2009'
...