The Complexity of Mean-Payoff Automaton Expression

Details The Complexity of Mean-Payoff Automaton Expression The Complexity of Mean-Payoff Automaton Expression

2011-06-15

arxiv.org/abs/1106.3054v1

Computer Science

Logic in Computer Science

Scientific paper

"Quantitative languages are 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. The class of \emph{mean-payoff automaton expressions}, introduced in [1], is a class of quantitative languages, which is robust: it is closed under the four pointwise operations of max, min, sum and numerical complement."[1] In this paper we improve the computational complexity for solving the classical decision problems for mean-payoff automaton expressions: while the previously best known upper bound was 4EXPTIME, and no lower bound was known, we give an optimal PSPACE complete bound. As a consequence we also obtain a conceptually simple algorithm to solve the classical decision problems for mean-payoff automaton expressions.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Mean-Payoff Automaton Expression does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Mean-Payoff Automaton Expression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Mean-Payoff Automaton Expression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-659893