Expressiveness and closure properties for quantitative languages
Chatterjee K, Doyen L, Henzinger TA. 2010. Expressiveness and closure properties for quantitative languages. Logical Methods in Computer Science. 6(3), 1–23.
Download
IST-2012-55-v1+1_Expressiveness_Closure_Properties_Quantitative_Languages.pdf
216.60 KB
[Published Version]
IST-2016-55-v2+1_1007.4018.pdf
302.42 KB
Journal Article
| Published
| English
Scopus indexed
Author
Department
Abstract
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. The value of a word w is the supremum of the values of the runs over w. 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 omega-regular for deterministic limit-average and discounted-sum automata, while this set is always omega-regular when the threshold is isolated (i.e., some neighborhood around the threshold contains no word). In the latter case, we prove that the omega-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.
Publishing Year
Date Published
2010-08-30
Journal Title
Logical Methods in Computer Science
Volume
6
Issue
3
Page
1 - 23
IST-REx-ID
Cite this
Chatterjee K, Doyen L, Henzinger TA. Expressiveness and closure properties for quantitative languages. Logical Methods in Computer Science. 2010;6(3):1-23. doi:10.2168/LMCS-6(3:10)2010
Chatterjee, K., Doyen, L., & Henzinger, T. A. (2010). Expressiveness and closure properties for quantitative languages. Logical Methods in Computer Science. International Federation of Computational Logic. https://doi.org/10.2168/LMCS-6(3:10)2010
Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Expressiveness and Closure Properties for Quantitative Languages.” Logical Methods in Computer Science. International Federation of Computational Logic, 2010. https://doi.org/10.2168/LMCS-6(3:10)2010.
K. Chatterjee, L. Doyen, and T. A. Henzinger, “Expressiveness and closure properties for quantitative languages,” Logical Methods in Computer Science, vol. 6, no. 3. International Federation of Computational Logic, pp. 1–23, 2010.
Chatterjee K, Doyen L, Henzinger TA. 2010. Expressiveness and closure properties for quantitative languages. Logical Methods in Computer Science. 6(3), 1–23.
Chatterjee, Krishnendu, et al. “Expressiveness and Closure Properties for Quantitative Languages.” Logical Methods in Computer Science, vol. 6, no. 3, International Federation of Computational Logic, 2010, pp. 1–23, doi:10.2168/LMCS-6(3:10)2010.
All files available under the following license(s):
Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0):
Main File(s)
File Name
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
0243da726476817f2ea33b48b78be696
File Name
IST-2016-55-v2+1_1007.4018.pdf
302.42 KB
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
5e512b8503a9cb263de26331c4ee9cf2