Cover Image

A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Suilen, Marnix, van der Vegt, Marck, Junges, Sebastian
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Robust Almost-Sure Reachability in Multi-Environment MDPs
by: van der Vegt, Marck, et al.
Published: (2023)

Compositional Verification of Almost-Sure Büchi Objectives in MDPs
by: van der Vegt, Marck, et al.
Published: (2025)

Pareto Curves for Compositionally Model Checking String Diagrams of MDPs
by: Watanabe, Kazuki, et al.
Published: (2024)

Compositional Value Iteration with Pareto Caching
by: Watanabe, Kazuki, et al.
Published: (2024)

On the Complexity of Robust Markov Decision Processes and Bisimulation Metrics
by: Suilen, Marnix, et al.
Published: (2026)

Fast Computation of Conditional Probabilities in MDPs and Markov Chain Families
by: Češka, Milan, et al.
Published: (2026)

Algorithm and Strategy Construction for Sure-Almost-Sure Stochastic Parity Games
by: Doyen, Laurent, et al.
Published: (2026)

Tractable Hyperproperties for MDPs
by: Gerlach, Lina, et al.
Published: (2026)

Small Decision Trees for MDPs with Deductive Synthesis
by: Andriushchenko, Roman, et al.
Published: (2025)

Policies Grow on Trees: Model Checking Families of MDPs
by: Andriushchenko, Roman, et al.
Published: (2024)

The Value Problem for Multiple-Environment MDPs with Parity Objective
by: Chatterjee, Krishnendu, et al.
Published: (2025)

Shields to Guarantee Probabilistic Safety in MDPs
by: Heck, Linus, et al.
Published: (2026)

Positive Almost-Sure Termination of Polynomial Random Walks
by: Winkler, Lorenz, et al.
Published: (2025)

Almost-Sure Termination by Guarded Refinement
by: Gregersen, Simon Oddershede, et al.
Published: (2024)

From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2023)

Multi-Environment MDPs with Prior and Universal Semantics
by: Bordais, Benjamin, et al.
Published: (2026)

Annotated Dependency Pairs for Full Almost-Sure Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2024)

The Annotated Dependency Pair Framework for Almost-Sure Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2024)

Almost Surely Asymptotically Constant Graph Neural Networks
by: Adam-Day, Sam, et al.
Published: (2024)

A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs
by: Perez, Mateo, et al.
Published: (2023)

Learning Robust Markov Models for Safe Runtime Monitoring
by: Skurka, Antonina, et al.
Published: (2026)

Learning Verified Monitors for Hidden Markov Models
by: van der Maas, Luko, et al.
Published: (2025)

A Complete Dependency Pair Framework for Almost-Sure Innermost Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2023)

From Innermost to Full Probabilistic Term Rewriting: Almost-Sure Termination, Complexity, and Modularity
by: Kassing, Jan-Christoph, et al.
Published: (2024)

Disproving (Positive) Almost-Sure Termination of Probabilistic Term Rewriting via Random Walks
by: Kassing, Jan-Christoph, et al.
Published: (2026)

Dependency Pairs for Expected Innermost Runtime Complexity and Strong Almost-Sure Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2025)

Small Test Suites for Active Automata Learning
by: Kruger, Loes, et al.
Published: (2024)

Relating Apartness and Branching Bisimulation Games
by: Rot, Jurriaan, et al.
Published: (2024)

Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs
by: Bovy, Eline M., et al.
Published: (2024)

Strategy Templates for Almost-Sure and Positive Winning of Stochastic Parity Games towards Permissive and Resilient Control
by: Phalakarn, Kittiphon, et al.
Published: (2024)

A Unifying Approach to Product Constructions for Quantitative Temporal Inference
by: Watanabe, Kazuki, et al.
Published: (2024)

The Equational Theory of Relational Kleene Algebra with Graph Loop is PSPACE-Complete
by: Nakamura, Yoshiki
Published: (2025)

Solving MDPs with LTLf+ and PPLTL+ Temporal Objectives
by: De Giacomo, Giuseppe, et al.
Published: (2025)

Towards Practical Zero-Knowledge Proof for PSPACE
by: Karthikeyan, Ashwin, et al.
Published: (2025)

State Matching and Multiple References in Adaptive Active Automata Learning
by: Kruger, Loes, et al.
Published: (2024)

Error-awareness Accelerates Active Automata Learning
by: Kruger, Loes, et al.
Published: (2026)

Generalised Quantifiers Based on Rabin-Mostowski Index
by: Kuperberg, Denis, et al.
Published: (2026)

CTMCs with Imprecisely Timed Observations
by: Badings, Thom, et al.
Published: (2024)

Efficient Probabilistic Model Checking for Relational Reachability (Extended Version)
by: Gerlach, Lina, et al.
Published: (2025)

Verifying Quantized Graph Neural Networks is PSPACE-complete
by: Sälzer, Marco, et al.
Published: (2025)