Model Checking CTL is Almost Always Inherently Sequential

Details Model Checking CTL is Almost Always Inherently Sequential Model Checking CTL is Almost Always Inherently Sequential

2011-03-25

arxiv.org/abs/1103.4990v3

LMCS 7 (2:12) 2011

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-7(2:12)2011

The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the use of temporal modalities or the use of negations---restrictions already studied for LTL by Sistla and Clarke (1985) and Markey (2004). For all these fragments, except for the trivial case without any temporal operator, we systematically prove model checking to be either inherently sequential (P-complete) or very efficiently parallelizable (LOGCFL-complete). For most fragments, however, model checking for CTL is already P-complete. Hence our results indicate that, in cases where the combined complexity is of relevance, approaching CTL model checking by parallelism cannot be expected to result in any significant speedup. We also completely determine the complexity of the model checking problem for all fragments of the extensions ECTL, CTL+, and ECTL+.

Affiliated with

Also associated with

No associations

Rating

Model Checking CTL is Almost Always Inherently Sequential 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 Model Checking CTL is Almost Always Inherently Sequential, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Model Checking CTL is Almost Always Inherently Sequential will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-571062