Document Open Access Logo

Finite-Valued Weighted Automata

Authors Emmanuel Filiot, Raffaella Gentilini, Jean-Francois Raskin

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.133.pdf
  • Filesize: 484 kB
  • 13 pages

Document Identifiers

Author Details

Emmanuel Filiot
Raffaella Gentilini
Jean-Francois Raskin

Cite As Get BibTex

Emmanuel Filiot, Raffaella Gentilini, and Jean-Francois Raskin. Finite-Valued Weighted Automata. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 133-145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.133

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.

Subject Classification

Keywords
  • Nested word
  • Transducer
  • Streaming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. U. Boker and T. A. Henzinger. Determinizing discounted-sum automata. In CSL, pages 82-96, 2011. Google Scholar
  2. V. Bruyère, N. Meunier, and J-F. Raskin. Secure equilibria in weighted games. In LICS, 2014. to appear. Google Scholar
  3. K. Chatterjee, L. Doyen, and T. A. Henzinger. Quantitative languages. ACM Trans. Comput. Log, 11(4), 2010. Google Scholar
  4. K. Chatterjee, V. Forejt, and D. Wojtczak. Multi-objective discounted reward verification in graphs and mdps. In LPAR, pages 228-242, 2013. Google Scholar
  5. C. Choffrut. Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles. Theor. Comput. Sci., 5(3):325-337, 1977. Google Scholar
  6. E. Clarke, O. Grumberg, and D. Peled. Model Checking. The MIT Press, Cambridge, Massachusetts, 1999. Google Scholar
  7. R. de Souza. On the decidability of the equivalence for k-valued transducers. In Developments in Language Theory, pages 252-263, 2008. Google Scholar
  8. R. de Souza and N. Kobayashi. A combinatorial study of k-valued rational relations. Journal of Automata, Languages and Combinatorics, 3/4(13):207-231, 2008. Google Scholar
  9. M. Droste, W. Kuich, and H. Vogler. HandBook of Weighted Automata. Springer, 2009. Google Scholar
  10. E. Filiot, R. Gentilini, and J-F. Raskin. Quantitative languages defined by functional automata. In CONCUR, pages 132-146, 2012. Google Scholar
  11. T. V. Griffiths. The unsolvability of the equivalence problem for -free nondeterministic generalized machines. Journal of the ACM, 1968. Google Scholar
  12. E. Gurari and O. Ibarra. A note on finitely-valued and finitely ambiguous transducers. Mathematical Systems Theory, 16(1):61-66, 1983. Google Scholar
  13. K. Hashiguchi, K. Ishiguro, and S. Jimbo. Decidability of the equivalence problem for finitely ambiguous finance automata. IJAC, 12(3):445, 2002. Google Scholar
  14. I. Klimann, S. Lombardy, J. Mairesse, and C. Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. TCS, 327(3):349-373, 2004. Google Scholar
  15. D. Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Int. Journal of Algebra and Computation, 4(3):405-425, 1994. Google Scholar
  16. M. L. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967. Google Scholar
  17. K. S. Rao and G. Sullivan. Detecting cycles in dynamic graphs in polynomial time. In Proc. STOC'88, STOC, pages 398-406. ACM, 1988. Google Scholar
  18. J. Sakarovitch and R. de Souza. On the decidability of bounded valuedness for transducers. In Proc. MFCS 2008, MFCS. Springer-Verlag, 2008. Google Scholar
  19. J. Sakarovitch and R. de Souza. Lexicographic decomposition of k -valued transducers. Theory Comput. Syst, 47(3):758-785, 2010. Google Scholar
  20. H. Seidl. Equivalence of finite-valued tree transducers is decidable. Mathematical Systems Theory, 27(4):285-346, 1994. Google Scholar
  21. A. Weber. On the valuedness of finite transducers. Acta Informatica, 27(8):749-780, 1989. Google Scholar
  22. A. Weber. Finite-valued distance automata. TCS, 134(1):225-251, 7 November 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact