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. Journal articles
  4. Quantitative Languages
 
research article

Quantitative Languages

Chatterjee, Krishnendu
•
Doyen, Laurent
•
Henzinger, Thomas A.  
2010
Acm Transactions On Computational Logic

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.

  • Details
  • Metrics
Type
research article
DOI
10.1145/1805950.1805953
Web of Science ID

WOS:000280546300003

Author(s)
Chatterjee, Krishnendu
Doyen, Laurent
Henzinger, Thomas A.  
Date Issued

2010

Published in
Acm Transactions On Computational Logic
Volume

11

Issue

4

Start page

23

Subjects

Verification

•

Model checking

•

expressiveness

•

quantitative verification

•

weighted automata

•

Weighted Automata

•

Stochastic Games

•

Logics

•

Complexity

•

Payoff

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
MTC  
Available on Infoscience
December 16, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/75305
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