Quantitative Languages Defined by Functional Automata

Details Quantitative Languages Defined by Functional Automata Quantitative Languages Defined by Functional Automata

2011-09-24

arxiv.org/abs/1111.0862v2

Computer Science

Formal Languages and Automata Theory

(2011)

Scientific paper

In this paper, we study several decision problems for functional weighted automata. To associate values with runs, we consider four different measure functions: the sum, the mean, the discounted sum of weights along edges and the ratio between rewards and costs. On the positive side, we show that the existential and universal threshold problems, the language inclusion problem and the equivalence problem are all decidable for the class of functional weighted automata and the four measure functions that we consider. On the negative side, we also study the quantitative extension of the realizability problem and show that it is undecidable for sum, mean and ratio. Finally, we show how to decide if the quantitative language defined by a functional weighted discounted sum automaton can be defined with a deterministic automata (it was already known for sum and mean).

Affiliated with

Also associated with

No associations

Rating

Quantitative Languages Defined by Functional Automata 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 Quantitative Languages Defined by Functional Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantitative Languages Defined by Functional Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-602749