Pushdown Processes: Games and Model Checking
Igor Walukiewicz · BRICS Report Series · 1996
Games given by transition graphs of pushdown processes are considered. It is shown that if there is a winning strategy in such a game then there is a winning strategy that is realized by a pushdown process. This fact turns out to be connected with the model checking problem for the pushdown automata and the propositional mu-calculus. It is shown that this model checking problem is DEXPTIME-complete.
Cited by 93 works. doi:10.7146/brics.v3i54.20057 Open-access PDF
Authors
References
- EFFICIENT MODEL CHECKING IN FRAGMENTS OF THE PROPOSITIONAL MU-CALCULUS.
- Tree automata, mu-calculus and determinacy
- Verification tools for finite-state concurrent systems
- On the synthesis of strategies in infinite games
- The theory of ends, pushdown automata, and second-order logic
- Model checking for context-free processes
- An improved algorithm for the evaluation of fixpoint expressions
- Process theory based on bisimulation semantics
- An automata-theoretic approach to fair realizability and synthesis
- Monadic second-order logic on tree-like structures