License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.133
URN: urn:nbn:de:0030-drops-48388
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4838/
Go to the corresponding LIPIcs Volume Portal

Filiot, Emmanuel ; Gentilini, Raffaella ; Raskin, Jean-Francois

Finite-Valued Weighted Automata

pdf-format:
14.pdf (0.5 MB)

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 k-valued 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 k-valued automata, for all parameters k. We consider several measures to associate values with runs: sum, discounted-sum, 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 k-valued. We also show that any k-valued 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 sum-automata, we show, based on this decomposition, that they are decidable for k-valued sum-automata, and k-valued discounted sum-automata over inverted integer discount factors. We finally show that the quantitative Church problem is undecidable for k-valued sum-automata, even given as finite unions of deterministic sum-automata.

BibTeX - Entry

@InProceedings{filiot_et_al:LIPIcs:2014:4838,
  author =	{Emmanuel Filiot and Raffaella Gentilini and Jean-Francois Raskin},
  title =	{{Finite-Valued Weighted Automata}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{133--145},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4838},
  URN =		{urn:nbn:de:0030-drops-48388},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.133},
  annote =	{Keywords: Nested word, Transducer, Streaming}
}

Keywords: Nested word, Transducer, Streaming
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI