Filiot, Emmanuel ;
Gentilini, Raffaella ;
Raskin, JeanFrancois
FiniteValued Weighted Automata
Abstract
Any weighted automaton (WA) defines a relation from finite words to values: given an input word, its set of values is obtained as the set of values computed by each accepting run on that word. A WA is kvalued if the relation it defines has degree at most k, i.e., every set of values associated with an input word has cardinality at most k. We investigate the class of quantitative languages defined by kvalued automata, for all parameters k. We consider several measures to associate values with runs: sum, discountedsum, and more generally values in groups.
We define a general procedure which decides, given a bound k and a WA over a group, whether this automaton is kvalued. We also show that any kvalued WA over a group, under some general conditions, can be decomposed as a union of k unambiguous WA. While inclusion and equivalence are undecidable problems for arbitrary sumautomata, we show, based on this decomposition, that they are decidable for kvalued sumautomata, and kvalued discounted sumautomata over inverted integer discount factors. We finally show that the quantitative Church problem is undecidable for kvalued sumautomata, even given as finite unions of deterministic sumautomata.
BibTeX  Entry
@InProceedings{filiot_et_al:LIPIcs:2014:4838,
author = {Emmanuel Filiot and Raffaella Gentilini and JeanFrancois Raskin},
title = {{FiniteValued Weighted Automata}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {133145},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897774},
ISSN = {18688969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4838},
URN = {urn:nbn:de:0030drops48388},
doi = {10.4230/LIPIcs.FSTTCS.2014.133},
annote = {Keywords: Nested word, Transducer, Streaming}
}
2014
Keywords: 

Nested word, Transducer, Streaming 
Seminar: 

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Issue date: 

2014 
Date of publication: 

2014 