Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Logic in computer science (03B70)
Abstract: The paper studies a probabilistic notion of causes in Markov chains that relies on the counterfactuality principle and the probability-raising property. This notion is motivated by the use of causes for monitoring purposes where the aim is to detect faulty or undesired behaviours before they actually occur. A cause is a set of finite executions of the system after which the probability of the effect exceeds a given threshold. We introduce multiple types of costs that capture the consumption of resources from different perspectives, and study the complexity of computing cost-minimal causes.
Recommendations
Cites work
- scientific article; zbMATH DE number 5585443 (Why is no real title available?)
- scientific article; zbMATH DE number 2243367 (Why is no real title available?)
- A proposed probabilistic extension of the Halpern and Pearl definition of `actual cause'
- An Analysis of Stochastic Shortest Path Problems
- An LTL proof system for runtime verification
- CP-logic: A language of causal probabilistic events and its relation to logic programming
- Causality. Models, reasoning, and inference
- Causes and explanations in the structural-model approach: Tractable cases
- Complexity results for explanations in the structural-model approach
- Computational Complexity of Probabilistic Turing Machines
- Embracing events in causal modelling: interventions and counterfactuals in CP-logic
- Explaining Counterexamples Using Causality
- Explanation in artificial intelligence: insights from the social sciences
- Monitoring Temporal Properties of Stochastic Systems
- Monitoring the Full Range of ω-Regular Properties of Stochastic Systems
- On the expressiveness and complexity of randomization in finite state monitors
- PP is as Hard as the Polynomial-Time Hierarchy
- Partial and conditional expectations in Markov decision processes with integer weights
- Probabilistic Causality
- Spanning the spectrum from safety to liveness
- The complexity of the Kth largest subset problem and related problems
- The cost of exactness in quantitative reachability
- The odds of staying on budget
- To reach or not to reach? Efficient algorithms for total-payoff games
- What causes a system to satisfy a specification?
Cited in
(6)- On probability-raising causality in Markov decision processes
- Foundations of probability-raising causality in Markov decision processes
- Probabilistic causation in branching time
- Operational causality -- necessarily sufficient and sufficiently necessary
- Temporal causality in reactive systems
- Probabilistic Causality
This page was built for publication: Probabilistic causes in Markov chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2147196)
