Non-deterministic Weighted Automata on Random Words

DOI10.4230/LIPICS.CONCUR.2018.10MaRDI QIDQ5009422zbMATH OpenOpenAlexFDO

Authors Jakub Michaliszyn, Jan Otop

Publication date 4 August 2021

Full work available at URL https://doi.org/10.4230/LIPIcs.CONCUR.2018.10

zbMATH Keywords

expected valueweighted automataquantitative verification

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Stochastization of weighted automata
• Non-deterministic weighted automata evaluated over Markov chains
• scientific article; zbMATH DE number 7559401
• Finitely nonstationary nondeterministic automata with random input
• On deterministic weighted automata
• On the Rademacher complexity of weighted automata
• On the determinization of weighted finite automata
• scientific article; zbMATH DE number 1223726
• Random deterministic automata
• Probabilistic Weighted Automata

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• A Survey of Stochastic Games with Limsup and Liminf Objectives
• Approximate determinization of quantitative automata
• Handbook of model checking
• Handbook of weighted automata
• Markov chains and unambiguous Büchi automata
• Model measuring for discrete and hybrid systems
• Percentile queries in multi-dimensional Markov decision processes
• Predicate abstraction and refinement for verifying multi-threaded programs
• Quantitative languages
• Reasoning about online algorithms with weighted automata
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• The Cost of Traveling between Languages
• The complexity of computing the permanent
• The complexity of probabilistic verification
• What's decidable about weighted automata?

Cited in

(9)

• Approximate learning of limit-average automata
• Probabilistic Weighted Automata
• Limited non-determinism hierarchy of counter automata
• Non-deterministic weighted automata evaluated over Markov chains
• The big-O problem
• The big-O problem for labelled Markov chains and weighted automata
• Stochastization of weighted automata
• Convex language semantics for nondeterministic probabilistic automata
• Finitely nonstationary nondeterministic automata with random input

Describes a project that uses

Uses Software

• PRISM

This page was built for publication: Non-deterministic Weighted Automata on Random Words

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