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 systemsMarkov decision processesnondeterminismpartial observationprobabilistic systemsinterleaving

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1863173 (Why is no real title available?)
• A framework for analyzing probabilistic protocols and its application to the partial secrets exchange
• Composition and behaviors of probabilistic I/O automata
• 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

(9)

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

Describes a project that uses

Uses Software

• LiQuor
• PRISM

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)