The Value 1 Problem for Probabilistic Automata

I will discuss recent developments about algorithmic properties for probabilistic automata over finite words. This computation model is a generalization of (classical) automata, where transitions are stochastic. Despite its simple and natural definition, this model turns out to be very expressive, and since its introduction in 1963 many properties have been shown to be undecidable. Over the last years, there has been a renewned interested in probabilistic automata, with a focus on constructing algorithms to partially solve natural yet undecidable properties. I will discuss our attempts to understand what is decidable about the value 1 problem: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1?

Authors

• Nathanaël Fijalkow

Keywords

No keywords are indexed for this paper.