---
_id: '3853'
abstract:
- lang: eng
  text: 'Quantitative languages are an extension of boolean languages that assign
    to each word a real number. Mean-payoff automata are finite automata with numerical
    weights on transitions that assign to each infinite path the long-run average
    of the transition weights. When the mode of branching of the automaton is deterministic,
    nondeterministic, or alternating, the corresponding class of quantitative languages
    is not robust as it is not closed under the pointwise operations of max, min,
    sum, and numerical complement. Nondeterministic and alternating mean-payoff automata
    are not decidable either, as the quantitative generalization of the problems of
    universality and language inclusion is undecidable. We introduce a new class of
    quantitative languages, defined by mean-payoff automaton expressions, which is
    robust and decidable: it is closed under the four pointwise operations, and we
    show that all decision problems are decidable for this class. Mean-payoff automaton
    expressions subsume deterministic meanpayoff automata, and we show that they have
    expressive power incomparable to nondeterministic and alternating mean-payoff
    automata. We also present for the first time an algorithm to compute distance
    between two quantitative languages, and in our case the quantitative languages
    are given as mean-payoff automaton expressions.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Philippe
  full_name: Rannou, Philippe
  last_name: Rannou
citation:
  ama: 'Chatterjee K, Doyen L, Edelsbrunner H, Henzinger TA, Rannou P. Mean-payoff
    automaton expressions. In: Vol 6269. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2010:269-283. doi:<a href="https://doi.org/10.1007/978-3-642-15375-4_19">10.1007/978-3-642-15375-4_19</a>'
  apa: 'Chatterjee, K., Doyen, L., Edelsbrunner, H., Henzinger, T. A., &#38; Rannou,
    P. (2010). Mean-payoff automaton expressions (Vol. 6269, pp. 269–283). Presented
    at the CONCUR: Concurrency Theory, Paris, France: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.1007/978-3-642-15375-4_19">https://doi.org/10.1007/978-3-642-15375-4_19</a>'
  chicago: Chatterjee, Krishnendu, Laurent Doyen, Herbert Edelsbrunner, Thomas A Henzinger,
    and Philippe Rannou. “Mean-Payoff Automaton Expressions,” 6269:269–83. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2010. <a href="https://doi.org/10.1007/978-3-642-15375-4_19">https://doi.org/10.1007/978-3-642-15375-4_19</a>.
  ieee: 'K. Chatterjee, L. Doyen, H. Edelsbrunner, T. A. Henzinger, and P. Rannou,
    “Mean-payoff automaton expressions,” presented at the CONCUR: Concurrency Theory,
    Paris, France, 2010, vol. 6269, pp. 269–283.'
  ista: 'Chatterjee K, Doyen L, Edelsbrunner H, Henzinger TA, Rannou P. 2010. Mean-payoff
    automaton expressions. CONCUR: Concurrency Theory, LNCS, vol. 6269, 269–283.'
  mla: Chatterjee, Krishnendu, et al. <i>Mean-Payoff Automaton Expressions</i>. Vol.
    6269, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 269–83, doi:<a
    href="https://doi.org/10.1007/978-3-642-15375-4_19">10.1007/978-3-642-15375-4_19</a>.
  short: K. Chatterjee, L. Doyen, H. Edelsbrunner, T.A. Henzinger, P. Rannou, in:,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 269–283.
conference:
  end_date: 2010-09-03
  location: Paris, France
  name: 'CONCUR: Concurrency Theory'
  start_date: 2010-08-31
corr_author: '1'
date_created: 2018-12-11T12:05:31Z
date_published: 2010-11-18T00:00:00Z
date_updated: 2024-10-09T20:54:08Z
day: '18'
ddc:
- '000'
- '005'
department:
- _id: KrCh
- _id: HeEd
- _id: ToHe
doi: 10.1007/978-3-642-15375-4_19
ec_funded: 1
file:
- access_level: open_access
  checksum: 4f753ae99d076553fb8733e2c8b390e2
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:15:41Z
  date_updated: 2020-07-14T12:46:17Z
  file_id: '5163'
  file_name: IST-2012-62-v1+1_Mean-payoff_automaton_expressions.pdf
  file_size: 233260
  relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
fulldoi: https://doi.org/10.1007/978-3-642-15375-4_19
has_accepted_license: '1'
intvolume: '      6269'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
page: 269 - 283
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '215543'
  name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '214373'
  name: Design for Embedded Systems
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2328'
pubrep_id: '62'
quality_controlled: '1'
scopus_import: 1
status: public
title: Mean-payoff automaton expressions
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6269
year: '2010'
...