Document Open Access Logo

Probabilistic Automata of Bounded Ambiguity

Authors Nathanaël Fijalkow, Cristian Riveros, James Worrell

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2017.19.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Nathanaël Fijalkow
Cristian Riveros
James Worrell

Cite AsGet BibTex

Nathanaël Fijalkow, Cristian Riveros, and James Worrell. Probabilistic Automata of Bounded Ambiguity. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CONCUR.2017.19

Abstract

Probabilistic automata are a computational model introduced by Michael Rabin, extending nondeterministic finite automata with probabilistic transitions. Despite its simplicity, this model is very expressive and many of the associated algorithmic questions are undecidable. In this work we focus on the emptiness problem, which asks whether a given probabilistic automaton accepts some word with probability higher than a given threshold. We consider a natural and well-studied structural restriction on automata, namely the degree of ambiguity, which is defined as the maximum number of accepting runs over all words. We observe that undecidability of the emptiness problem requires infinite ambiguity and so we focus on the case of finitely ambiguous probabilistic automata. Our main results are to construct efficient algorithms for analysing finitely ambiguous probabilistic automata through a reduction to a multi-objective optimisation problem, called the stochastic path problem. We obtain a polynomial time algorithm for approximating the value of finitely ambiguous probabilistic automata and a quasi-polynomial time algorithm for the emptiness problem for 2-ambiguous probabilistic automata.
Keywords
  • Probabilistic Automata
  • Emptiness Problem
  • Stochastic Path Problem
  • Multi-Objective Optimisation Problems

Metrics

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

References

  1. Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the complexity of numerical analysis. SIAM Journal on Computing, 38(5):1987-2006, 2009. Google Scholar
  2. Alberto Bertoni. The solution of problems relative to probabilistic automata in the frame of the formal languages theory. In GI Jahrestagung, pages 107-112, 1974. Google Scholar
  3. Patricia June Carstensen. The Complexity of Some Problems in Parametric Linear and Combinatorial Programming. PhD thesis, University of Michigan, 1983. Google Scholar
  4. Rohit Chadha, A. Prasad Sistla, and Mahesh Viswanathan. Emptiness under isolation and the value problem for hierarchical probabilistic automata. In FoSSaCS, pages 231-247, 2017. Google Scholar
  5. Krishnendu Chatterjee and Mathieu Tracol. Decidable problems for probabilistic automata on infinite words. In LICS, pages 185-194, 2012. Google Scholar
  6. Ilias Diakonikolas and Mihalis Yannakakis. Succinct approximate convex pareto curves. In SODA, pages 74-83, 2008. Google Scholar
  7. Nathanaël Fijalkow, Hugo Gimbert, Edon Kelmendi, and Youssouf Oualhadj. Deciding the value 1 problem for probabilistic leaktight automata. Logical Methods in Computer Science, 11(2), 2015. Google Scholar
  8. Nathanaël Fijalkow, Hugo Gimbert, and Youssouf Oualhadj. Deciding the value 1 problem for probabilistic leaktight automata. In LICS, pages 295-304, 2012. Google Scholar
  9. Hugo Gimbert and Youssouf Oualhadj. Probabilistic automata on finite words: Decidable and undecidable problems. In ICALP (2), pages 527-538, 2010. Google Scholar
  10. Daniel Mier Gusfield. Sensitivity Analysis for Combinatorial Optimization. PhD thesis, University of California, Berkeley, 1980. Google Scholar
  11. Dexter Kozen. Lower bounds for natural proof systems. In FOCS, pages 254-266, 1977. Google Scholar
  12. Ranko Lazić and Sylvain Schmitz. The ideal view on Rackoff’s coverability technique. In International Workshop on Reachability Problems, pages 76-88. Springer, 2015. Google Scholar
  13. Rune B. Lyngsø and Christian N. S. Pedersen. The consensus string problem and the complexity of comparing hidden Markov models. Journal of Computer and System Sciences, 65(3):545-569, 2002. Google Scholar
  14. Christos H. Papadimitriou and Mihalis Yannakakis. On the approximability of trade-offs and optimal access of web sources. In FOCS, pages 86-92, 2000. Google Scholar
  15. Azaria Paz. Introduction to Probabilistic Automata. Academic Press, 1971. Google Scholar
  16. Michael O. Rabin. Probabilistic automata. Information and Control, 6(3):230-245, 1963. Google Scholar
  17. Keijo Ruohonen. Reversible machines and Post’s correspondence problem for biprefix morphisms. Elektronische Informationsverarbeitung und Kybernetik, 21(12):579-595, 1985. Google Scholar
  18. Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata. Theoretical Computer Science, 88(2):325-349, 1991. Google Scholar
  19. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1):103-128, 2007. 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 Imprint Privacy Contact