A space-efficient simulation algorithm on probabilistic automata

DOI10.1016/J.IC.2016.04.002MaRDI QIDQ2629854zbMATH OpenOpenAlexFDO

Authors David N. Jansen, Lijun Zhang

Publication date 7 July 2016

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2016.04.002

zbMATH Keywords

simulationprobabilistic automatapartition refinementdecision algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• A Space-Efficient Probabilistic Simulation Algorithm
• Saving space in a time efficient simulation algorithm
• An efficient simulation algorithm based on abstract interpretation

Cites work

• scientific article; zbMATH DE number 1614700 (Why is no real title available?)
• scientific article; zbMATH DE number 1705168 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 177519 (Why is no real title available?)
• scientific article; zbMATH DE number 1306878 (Why is no real title available?)
• scientific article; zbMATH DE number 1512606 (Why is no real title available?)
• scientific article; zbMATH DE number 794262 (Why is no real title available?)
• A Space-Efficient Probabilistic Simulation Algorithm
• Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation
• Bisimulation through probabilistic testing
• CCS expressions, finite state processes, and three problems of equivalence
• Characterising Testing Preorders for Finite Probabilistic Processes
• Comparative branching-time semantics for Markov chains
• Correcting a Space-Efficient Simulation Algorithm
• Deciding Simulations on Probabilistic Automata
• Deciding bisimilarity and similarity for probabilistic processes.
• Depth-First Search and Linear Graph Algorithms
• Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
• Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
• From bisimulation to simulation: Coarsest partition problems
• Improved Algorithms for Bipartite Network Flow
• Learning probabilistic systems from tree samples
• Logical Characterizations of Bisimulations for Discrete Probabilistic Systems
• Optimal state-space lumping in Markov chains
• Probabilistic logical characterization
• Probabilistic weak simulation is decidable in polynomial time
• Simple O(m n) time Markov chain lumping
• The dining cryptographers problem: Unconditional sender and recipient untraceability
• Three Partition Refinement Algorithms
• Transformational design and implementation of a new efficient solution to the ready simulation problem
• Verification of multiprocess probabilistic protocols
• Weak bisimulation is sound and complete for pCTL\(^*\)

Cited in

(3)

• A Space-Efficient Probabilistic Simulation Algorithm
• An efficient algorithm to determine probabilistic bisimulation
• Space-bounded probabilistic game automata

Describes a project that uses

Uses Software

• PRISM

This page was built for publication: A space-efficient simulation algorithm on probabilistic automata

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