Quantitative languages

Chatterjee K, Doyen L, Henzinger TA. 2010. Quantitative languages. ACM Transactions on Computational Logic (TOCL). 11(4), 23.

Download
OA IST-2012-57-v1+1_Quantitative_languages.pdf 169.14 KB [Submitted Version]

Journal Article | Published | English

Scopus indexed
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.
Publishing Year
Date Published
2010-07-01
Journal Title
ACM Transactions on Computational Logic (TOCL)
Publisher
ACM
Volume
11
Issue
4
Article Number
23
IST-REx-ID

Cite this

Chatterjee K, Doyen L, Henzinger TA. Quantitative languages. ACM Transactions on Computational Logic (TOCL). 2010;11(4). doi:10.1145/1805950.1805953
Chatterjee, K., Doyen, L., & Henzinger, T. A. (2010). Quantitative languages. ACM Transactions on Computational Logic (TOCL). ACM. https://doi.org/10.1145/1805950.1805953
Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Quantitative Languages.” ACM Transactions on Computational Logic (TOCL). ACM, 2010. https://doi.org/10.1145/1805950.1805953.
K. Chatterjee, L. Doyen, and T. A. Henzinger, “Quantitative languages,” ACM Transactions on Computational Logic (TOCL), vol. 11, no. 4. ACM, 2010.
Chatterjee K, Doyen L, Henzinger TA. 2010. Quantitative languages. ACM Transactions on Computational Logic (TOCL). 11(4), 23.
Chatterjee, Krishnendu, et al. “Quantitative Languages.” ACM Transactions on Computational Logic (TOCL), vol. 11, no. 4, 23, ACM, 2010, doi:10.1145/1805950.1805953.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
f2e50bbd6871fba0aec30bd9625a1ee7


Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar