---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Laurent
foaf_name: Doyen, Laurent
foaf_surname: Doyen
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
bibo_doi: 10.1007/978-3-642-03409-1_2
bibo_volume: 5699
dct_date: 2009^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Alternating weighted automata@
...