Friday 6th May, 12:15, room 310

posted 4 May 2016, 03:56 by Jakub Michaliszyn
Jan Otop   

Quantitative Automata under Probabilistic Semantics

Automata with monitor counters, where the transitions do not
depend on counter values, and nested weighted automata are
two expressive automata-theoretic frameworks for quantitative
For a well-studied and wide class of quantitative functions,
we establish that automata with monitor counters and nested weighted
automata are equivalent.
We study for the first time such quantitative automata under
probabilistic semantics.
We show that several problems that are undecidable for the
classical questions of emptiness and universality become
decidable under the probabilistic semantics.
We present a complete picture of decidability for such automata,
and even an almost-complete picture of computational complexity,
for the probabilistic questions we consider.