𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Model checking propositional dynamic logic with all extras

✍ Scribed by Martin Lange

Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
116 KB
Volume
4
Category
Article
ISSN
1570-8683

No coin nor oath required. For personal study only.

✦ Synopsis

This paper presents a model checking algorithm for Propositional Dynamic Logic (PDL) with looping, repeat, test, intersection, converse, program complementation as well as context-free programs. The algorithm shows that the model checking problem for PDL remains PTIME-complete in the presence of all these operators, in contrast to the high increase in complexity that they cause for the satisfiability problem.

πŸ“œ SIMILAR VOLUMES

Parallel propositional satisfiability ch
Parallel propositional satisfiability checking with distributed dynamic learning
✍ Wolfgang Blochinger; Carsten Sinz; Wolfgang KΓΌchlin πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 897 KB

We address the parallelization and distributed execution of an algorithm from the area of symbolic computation: propositional satisfiability (SAT) checking with dynamic learning. Our parallel programming models are strict multithreading for the core SAT checking procedure, complemented by mobile age