--- _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' ...