Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||
| DOI | 10.4230/LIPICS.CONCUR.2017.19 | ||
| Año | 2017 | ||
| Tipo |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
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.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | Fijalkow, Nathanaël | - |
Alan Turing Institute - Reino Unido
The University of Warwick - Reino Unido University of Warwick - Reino Unido |
| 2 | Riveros, Cristian | Hombre |
Pontificia Universidad Católica de Chile - Chile
|
| 3 | Worrell, James | Hombre |
University of Oxford - Reino Unido
|
| Fuente |
|---|
| Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica |
| Engineering and Physical Sciences Research Council |
| Millennium Nucleus Center for Semantic Web Research |
| Alan Turing Institute |