Author(s):

Chatterjee, Krishnendu; Doyen, Laurent; Edelsbrunner, Herbert; Henzinger, Thomas A; Rannou, Philippe

Title: 
Meanpayoff automaton expressions

Title Series: 
LNCS

Affiliation 
IST Austria 
Abstract: 
Quantitative languages are an extension of boolean languages that assign to each word a real number. Meanpayoff automata are finite automata with numerical weights on transitions that assign to each infinite path the longrun 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 meanpayoff 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 meanpayoff 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. Meanpayoff automaton expressions subsume deterministic meanpayoff automata, and we show that they have expressive power incomparable to nondeterministic and alternating meanpayoff 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 meanpayoff automaton expressions.

Conference Title:

CONCUR: Concurrency Theory

Volume: 
6269

Conference Dates:

August 31  September 3, 2010

Conference Location:

Paris, France

ISBN:

9783959770170

Publisher:

Schloss Dagstuhl  LeibnizZentrum für Informatik

Location:

Berlin, Heidelberg

Date Published:

20101118

Start Page: 
269

End Page:

283

Sponsor: 
This research was supported by EPFL, IST Austria, LSV@ENS Cachan & CNRS, and the following grants: the European Union project COMBEST, the European Network of Excellence ArtistDesign, the DARPA grant HR00110510057, and the NSF grant DBI0820624.

URL: 

DOI: 
10.1007/9783642153754_19

Open access: 
yes (repository) 