---
_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:10.1007/978-3-642-03409-1_2'
apa: 'Chatterjee, K., Doyen, L., & Henzinger, T. A. (2009). Alternating weighted
automata (Vol. 5699, pp. 3–13). Presented at the FCT: Fundamentals of Computation
Theory, Wroclaw, Poland: Springer. https://doi.org/10.1007/978-3-642-03409-1_2'
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Alternating
Weighted Automata,” 5699:3–13. Springer, 2009. https://doi.org/10.1007/978-3-642-03409-1_2.
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. *Alternating Weighted Automata*. Vol. 5699,
Springer, 2009, pp. 3–13, doi:10.1007/978-3-642-03409-1_2.
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
date_created: 2018-12-11T12:09:23Z
date_published: 2009-09-10T00:00:00Z
date_updated: 2020-08-11T10:10:13Z
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'
...