Non-deterministic weighted automata evaluated over Markov chains

DOI10.1016/J.JCSS.2019.10.001MaRDI QIDQ2009651zbMATH OpenOpenAlexWikidataFDO

Authors Jakub Michaliszyn, Jan Otop

Publication date 29 November 2019

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.04625

zbMATH Keywords

expected valuequantitative verificationweighted automata

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: We present the first study of non-deterministic weighted automata under probabilistic semantics. In this semantics words are random events, generated by a Markov chain, and functions computed by weighted automata are random variables. We consider the probabilistic questions of computing the expected value and the cumulative distribution for such random variables. The exact answers to the probabilistic questions for non-deterministic automata can be irrational and are uncomputable in general. To overcome this limitation, we propose approximation algorithms for the probabilistic questions, which work in exponential time in the size of the automaton and polynomial time in the size of the Markov chain and the given precision. We apply this result to show that non-deterministic automata can be effectively determinised with respect to the standard deviation metric.

Recommendations

• Stochastization of weighted automata
• Non-deterministic Weighted Automata on Random Words
• On the determinization of weighted finite automata
• scientific article; zbMATH DE number 1223726
• On deterministic weighted automata
• Weighted automata
• Rigorous approximated determinization of weighted automata
• Probabilistic Weighted Automata
• scientific article; zbMATH DE number 2201363
• Markov chains and unambiguous automata

Cites work

• A Survey of Stochastic Games with Limsup and Liminf Objectives
• Approximate determinization of quantitative automata
• Convex language semantics for nondeterministic probabilistic automata
• Handbook of weighted automata
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3572058 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Markov chains and unambiguous Büchi automata
• Model measuring for discrete and hybrid systems
• Non-deterministic Weighted Automata on Random Words
• Optimal control of Markov processes with incomplete state information
• Percentile queries in multi-dimensional Markov decision processes
• Predicate abstraction and refinement for verifying multi-threaded programs
• Quantitative languages
• Rational approximations to algebraic numbers
• Reasoning about online algorithms with weighted automata
• The complexity of computing the permanent
• The complexity of probabilistic verification
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• What's decidable about weighted automata?

Cited in

(6)

• Stochastization of weighted automata
• Approximation of weighted automata with storage
• Rigorous approximated determinization of weighted automata
• Non-deterministic Weighted Automata on Random Words
• The big-O problem for labelled Markov chains and weighted automata
• Quantitative language automata

Describes a project that uses

Uses Software

• PRISM

This page was built for publication: Non-deterministic weighted automata evaluated over Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2009651)