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.CONCUR.2017.19
URN: urn:nbn:de:0030-drops-77716
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7771/
Go to the corresponding LIPIcs Volume Portal

Fijalkow, Nathanaël ; Riveros, Cristian ; Worrell, James

Probabilistic Automata of Bounded Ambiguity

pdf-format:
LIPIcs-CONCUR-2017-19.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{fijalkow_et_al:LIPIcs:2017:7771,
  author =	{Nathana{\"e}l Fijalkow and Cristian Riveros and James Worrell},
  title =	{{Probabilistic Automata of Bounded Ambiguity}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Roland Meyer and Uwe Nestmann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7771},
  URN =		{urn:nbn:de:0030-drops-77716},
  doi =		{10.4230/LIPIcs.CONCUR.2017.19},
  annote =	{Keywords: Probabilistic Automata, Emptiness Problem, Stochastic Path Problem, Multi-Objective Optimisation Problems}
}

Keywords: Probabilistic Automata, Emptiness Problem, Stochastic Path Problem, Multi-Objective Optimisation Problems
Collection: 28th International Conference on Concurrency Theory (CONCUR 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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