Quantitative Automata under Probabilistic Semantics

DOI10.1145/2933575.2933588zbMath1401.68155arXiv1604.06764OpenAlexW2342840234MaRDI QIDQ4635863

Krishnendu Chatterjee, Jan Otop, Thomas A. Henzinger

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

distributionMarkov chainsprobabilityexpected valueweighted automataprobabilistic semanticsnested weighted automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semantics in the theory of computing (68Q55) Decidability of theories and sets of sentences (03B25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (7)

Unnamed Item ⋮ Quantitative Automata under Probabilistic Semantics ⋮ Non-deterministic Weighted Automata on Random Words ⋮ Non-deterministic weighted automata evaluated over Markov chains ⋮ Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States ⋮ Monitor Logics for Quantitative Monitor Automata ⋮ Bidirectional nested weighted automata

Uses Software

• PRISM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Quantitative monitor automata
• Average-energy games
• Expressiveness and Closure Properties for Quantitative Languages
• Multi-objective Discounted Reward Verification in Graphs and MDPs
• Quantitative languages
• Temporal Specifications with Accumulative Values
• Quantitative Multi-objective Verification for Probabilistic Systems
• Energy and Mean-Payoff Parity Markov Decision Processes
• Alternating Weighted Automata
• Averaging in LTL
• Pebble Weighted Automata and Transitive Closure Logics
• Weighted Automata and Weighted Logics on Infinite Words
• A Survey of Stochastic Games with Limsup and Liminf Objectives
• Nested Weighted Limit-Average Automata of Bounded Width
• Trade-off analysis meets probabilistic model checking
• Weight monitoring with linear temporal logic
• Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
• Quantitative Automata under Probabilistic Semantics
• Non-deterministic Weighted Automata on Random Words
• Bidirectional nested weighted automata
• Regular Functions and Cost Register Automata
• Markov Decision Processes with Multiple Objectives
• Markov Decision Processes with Multiple Long-Run Average Objectives
• Discounting in LTL
• Measuring and Synthesizing Systems in Probabilistic Environments

This page was built for publication: Quantitative Automata under Probabilistic Semantics