Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. Expressiveness and Closure Properties for Quantitative Languages
 
report

Expressiveness and Closure Properties for Quantitative Languages

Chatterjee, Krishnendu
•
Doyen, Laurent
•
Henzinger, Thomas A.  
2008

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

  • Files
  • Details
  • Metrics
Type
report
Author(s)
Chatterjee, Krishnendu
•
Doyen, Laurent
•
Henzinger, Thomas A.  
Date Issued

2008

Written at

EPFL

EPFL units
MTC  
Available on Infoscience
February 8, 2008
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/17541
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés