---
res:
bibo_abstract:
- 'Quantitative languages are an extension of boolean languages that assign to each
word a real number. Mean-payoff automata are finite automata with numerical weights
on transitions that assign to each infinite path the long-run 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 mean-payoff 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 mean-payoff 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. Mean-payoff automaton expressions subsume deterministic
meanpayoff automata, and we show that they have expressive power incomparable
to nondeterministic and alternating mean-payoff 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 mean-payoff automaton
expressions.@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: Herbert
foaf_name: Edelsbrunner, Herbert
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- 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
- foaf_Person:
foaf_givenName: Philippe
foaf_name: Rannou, Philippe
foaf_surname: Rannou
bibo_doi: 10.1007/978-3-642-15375-4_19
bibo_volume: 6269
dct_date: 2010^xs_gYear
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Mean-payoff automaton expressions@
...