Filiot, Emmanuel and Gentilini, Raffaella and Raskin, Jean-François - Quantitative Languages Defined by Functional Automata

lmcs:1590 - Logical Methods in Computer Science, September 17, 2015, Volume 11, Issue 3
Quantitative Languages Defined by Functional Automata

Authors: Filiot, Emmanuel and Gentilini, Raffaella and Raskin, Jean-François

A weighted automaton is functional if any two accepting runs on the same finite word have the same value. In this paper, we investigate functional weighted automata for four different measures: 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 functionality is decidable for the four measures. Furthermore, the existential and universal threshold problems, the language inclusion problem and the equivalence problem are all decidable when the weighted automata are functional. 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. We finally show how to decide whether the language associated with a given functional automaton can be defined with a deterministic one, for sum, mean and discounted sum. The results on functionality and determinizability are expressed for the more general class of functional group automata. This allows one to formulate within the same framework new results related to discounted sum automata and known results on sum and mean automata. Ratio automata do not fit within this general scheme and different techniques are required to decide functionality.


Source : oai:arXiv.org:1111.0862
DOI : 10.2168/LMCS-11(3:14)2015
Volume: Volume 11, Issue 3
Published on: September 17, 2015
Submitted on: October 2, 2014
Keywords: Computer Science - Formal Languages and Automata Theory


Share

Consultation statistics

This page has been seen 109 times.
This article's PDF has been downloaded 31 times.