Distributed probabilistic input/output automata: expressiveness, (un)decidability and algorithms

DOI10.1016/J.TCS.2013.07.017MaRDI QIDQ2453112zbMATH OpenOpenAlexFDO

Authors Sergio Giro, Luis María Ferrer Fioriti, P. R. D'Argenio

Publication date 6 June 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.07.017

zbMATH Keywords

distributed systemsinterleavingMarkov decision processesnondeterminismpartial observationprobabilistic systems

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Quantitative Model Checking Revisited: Neither Decidable Nor Approximable
• Undecidability results for distributed probabilistic systems
• Partial Order Reduction for Probabilistic Systems: A Revision for Distributed Schedulers
• Advances in Computing Science – ASIAN 2003. Progamming Languages and Distributed Computation Programming Languages and Distributed Computation
• Quantitative Analysis of Randomized Distributed Systems and Probabilistic Automata

Cites work

• A framework for analyzing probabilistic protocols and its application to the partial secrets exchange
• Composition and behaviors of probabilistic I/O automata
• scientific article; zbMATH DE number 1863173 (Why is no real title available?)
• Information hiding in probabilistic concurrent systems
• On the undecidability of probabilistic planning and related stochastic optimization problems
• Partial Order Reduction for Probabilistic Systems: A Revision for Distributed Schedulers
• Quantitative Model Checking Revisited: Neither Decidable Nor Approximable
• Reactive, generative, and stratified models of probabilistic processes
• Retaining the probabilities in probabilistic testing theory
• Secure information flow by self-composition
• Switched PIOA: parallel composition via distributed scheduling
• The dining cryptographers problem: Unconditional sender and recipient untraceability
• Undecidability results for distributed probabilistic systems
• Verification of partial-information probabilistic systems using counterexample-guided refinements

Cited in

(10)

• Using schedulers to test probabilistic distributed systems
• The complexity of reachability in parametric Markov decision processes
• Distributed synthesis in continuous time
• Quantitative Analysis of Randomized Distributed Systems and Probabilistic Automata
• Partial Order Reduction for Probabilistic Systems: A Revision for Distributed Schedulers
• Quantitative Model Checking Revisited: Neither Decidable Nor Approximable
• Undecidability results for distributed probabilistic systems
• On the Complexity of Reachability in Parametric Markov Decision Processes
• Quantitative aspects of programming languages and systems over the past 2⁴ years and beyond
• Switched PIOA: parallel composition via distributed scheduling

Describes a project that uses

Uses Software

• PRISM
• LiQuor

This page was built for publication: Distributed probabilistic input/output automata: expressiveness, (un)decidability and algorithms

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