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. Quantitative Languages
 
report

Quantitative Languages

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

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 quantitative 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, 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 language inclusion remains open for some classes of quantitative automata, we introduce a notion of quantitative simulation that is decidable and implies language inclusion. We also compare the expressive powers of the various classes of quantitative automata. In particular, we show that most classes of quantitative automata cannot be determinized.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

technicalReport.pdf

Access type

openaccess

Size

296.52 KB

Format

Adobe PDF

Checksum (MD5)

f474adee34f0226c5dd9b0474188b3a3

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