---
_id: '4542'
abstract:
- lang: eng
  text: "Weighted automata are finite automata with numerical weights on transitions.
    Nondeterministic weighted automata define quantitative languages L that assign
    to each word w a real number L(w) computed as the maximal value of all runs over
    w, and the value of a run r is a function of the sequence of weights that appear
    along r. There are several natural functions to consider such as Sup, LimSup,
    LimInf, limit average, and discounted sum of transition weights.\r\nWe introduce
    alternating weighted automata in which the transitions of the runs are chosen
    by two players in a turn-based fashion. Each word is assigned the maximal value
    of a run that the first player can enforce regardless of the choices made by the
    second player. We survey the results about closure properties, expressiveness,
    and decision problems for nondeterministic weighted automata, and we extend these
    results to alternating weighted automata.\r\nFor quantitative languages L 1 and
    L 2, we consider the pointwise operations max(L 1,L 2), min(L 1,L 2), 1 − L 1,
    and the sum L 1 + L 2. We establish the closure properties of all classes of alternating
    weighted automata with respect to these four operations.\r\nWe next compare the
    expressive power of the various classes of alternating and nondeterministic weighted
    automata over infinite words. In particular, for limit average and discounted
    sum, we show that alternation brings more expressive power than nondeterminism.\r\nFinally,
    we present decidability results and open questions for the quantitative extension
    of the classical decision problems in automata theory: emptiness, universality,
    language inclusion, and language equivalence."
acknowledgement: This research was supported in part by the Swiss National Science
  Foundation under the Indo-Swiss Joint Research Programme, by the European Network
  of Excellence on Embedded Systems Design (ArtistDesign), by the European Combest,
  Quasimodo, and Gasics projects, by the PAI program Moves funded by the Belgian Federal
  Government, and by the CFV (Federated Center in Verification) funded by the F.R.S.-FNRS.
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: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
citation:
  ama: 'Chatterjee K, Doyen L, Henzinger TA. Alternating weighted automata. In: Vol
    5699. Springer; 2009:3-13. doi:<a href="https://doi.org/10.1007/978-3-642-03409-1_2">10.1007/978-3-642-03409-1_2</a>'
  apa: 'Chatterjee, K., Doyen, L., &#38; Henzinger, T. A. (2009). Alternating weighted
    automata (Vol. 5699, pp. 3–13). Presented at the FCT: Fundamentals of Computation
    Theory, Wroclaw, Poland: Springer. <a href="https://doi.org/10.1007/978-3-642-03409-1_2">https://doi.org/10.1007/978-3-642-03409-1_2</a>'
  chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Alternating
    Weighted Automata,” 5699:3–13. Springer, 2009. <a href="https://doi.org/10.1007/978-3-642-03409-1_2">https://doi.org/10.1007/978-3-642-03409-1_2</a>.
  ieee: 'K. Chatterjee, L. Doyen, and T. A. Henzinger, “Alternating weighted automata,”
    presented at the FCT: Fundamentals of Computation Theory, Wroclaw, Poland, 2009,
    vol. 5699, pp. 3–13.'
  ista: 'Chatterjee K, Doyen L, Henzinger TA. 2009. Alternating weighted automata.
    FCT: Fundamentals of Computation Theory, LNCS, vol. 5699, 3–13.'
  mla: Chatterjee, Krishnendu, et al. <i>Alternating Weighted Automata</i>. Vol. 5699,
    Springer, 2009, pp. 3–13, doi:<a href="https://doi.org/10.1007/978-3-642-03409-1_2">10.1007/978-3-642-03409-1_2</a>.
  short: K. Chatterjee, L. Doyen, T.A. Henzinger, in:, Springer, 2009, pp. 3–13.
conference:
  end_date: 2009-09-04
  location: Wroclaw, Poland
  name: 'FCT: Fundamentals of Computation Theory'
  start_date: 2009-09-02
corr_author: '1'
date_created: 2018-12-11T12:09:23Z
date_published: 2009-09-10T00:00:00Z
date_updated: 2024-10-09T20:53:55Z
day: '10'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.1007/978-3-642-03409-1_2
ec_funded: 1
file:
- access_level: open_access
  checksum: e8f53abb63579de3f2bff58b2a1188e2
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:15:09Z
  date_updated: 2020-07-14T12:46:31Z
  file_id: '5126'
  file_name: IST-2012-39-v1+1_Alternating_Weighted_Automata.pdf
  file_size: 164428
  relation: main_file
file_date_updated: 2020-07-14T12:46:31Z
has_accepted_license: '1'
intvolume: '      5699'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 3 - 13
project:
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '214373'
  name: Design for Embedded Systems
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '215543'
  name: COMponent-Based Embedded Systems design Techniques
publication_status: published
publisher: Springer
publist_id: '180'
pubrep_id: '39'
quality_controlled: '1'
scopus_import: 1
status: public
title: Alternating weighted automata
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5699
year: '2009'
...