Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Probabilistic automata of bounded ambiguity
Indexado
Scopus SCOPUS_ID:85030652799
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


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.

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Software
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



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

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



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

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
∗ This work was supported by The Alan Turing Institute under the EPSRC grant EP/N510129/1, by the EPSRC grant EP/M012298/1, by the FONDECYT grant 11150653 and the Millennium Nucleus Center for Semantic Web Research under grant NC120004.

Muestra la fuente de financiamiento declarada en la publicación.