Chatterjee, Krishnendu and Henzinger, Thomas A. and Otop, Jan - Quantitative Automata under Probabilistic Semantics

lmcs:4512 - Logical Methods in Computer Science, August 13, 2019, Volume 15, Issue 3
Quantitative Automata under Probabilistic Semantics

Authors: Chatterjee, Krishnendu and Henzinger, Thomas A. and Otop, Jan

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 properties. 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.


Source : oai:arXiv.org:1604.06764
Volume: Volume 15, Issue 3
Published on: August 13, 2019
Submitted on: May 16, 2018
Keywords: Computer Science - Formal Languages and Automata Theory


Share