Alternating weighted automata

Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A (2009) Alternating weighted automata. In: FCT: Fundamentals of Computation Theory, September 2-4, 2009, Wroclaw, Poland.

[img] Text
Alternating_Weighted_Automata.pdf - Accepted Version
Available under License All rights reserved.
[IST-2012-39-v1+1]
Download (160Kb)
Official URL: http://dx.doi.org/10.1007/978-3-642-03409-1_2

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. We 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. For 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. We 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. Finally, 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.

Item Type: Conference or Workshop Item (Paper)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 03 Oct 2012 09:00
Last Modified: 21 Sep 2017 11:22
URI: https://repository.ist.ac.at/id/eprint/39

Actions (login required)

View Item View Item