Symbolic model checking of tense logics on rational Kripke models

Details Symbolic model checking of tense logics on rational Kripke models Symbolic model checking of tense logics on rational Kripke models

2008-10-30

arxiv.org/abs/0810.5516v1

Computer Science

Logic in Computer Science

To appear in: Proceedings of the International Conference on Infinity in Logic and Computation ILC'2007, Springer LNAI

Scientific paper

We introduce the class of rational Kripke models and study symbolic model checking of the basic tense logic Kt and some extensions of it in models from that class. Rational Kripke models are based on (generally infinite) rational graphs, with vertices labeled by the words in some regular language and transitions recognized by asynchronous two-head finite automata, also known as rational transducers. Every atomic proposition in a rational Kripke model is evaluated in a regular set of states. We show that every formula of Kt has an effectively computable regular extension in every rational Kripke model, and therefore local model checking and global model checking of Kt in rational Kripke models are decidable. These results are lifted to a number of extensions of Kt. We study and partly determine the complexity of the model checking procedures.

Affiliated with

Also associated with

No associations

Rating

Symbolic model checking of tense logics on rational Kripke models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Symbolic model checking of tense logics on rational Kripke models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symbolic model checking of tense logics on rational Kripke models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-279038