Symbolic Reachability Analysis of Higher-Order Context-Free Processes

Details Symbolic Reachability Analysis of Higher-Order Context-Free Processes Symbolic Reachability Analysis of Higher-Order Context-Free Processes

2007-05-28

arxiv.org/abs/0705.3888v1

FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science (24/11/2004) 135-147

Computer Science

Logic in Computer Science

Scientific paper

10.1007/b104325

We consider the problem of symbolic reachability analysis of higher-order context-free processes. These models are generalizations of the context-free processes (also called BPA processes) where each process manipulates a data structure which can be seen as a nested stack of stacks. Our main result is that, for any higher-order context-free process, the set of all predecessors of a given regular set of configurations is regular and effectively constructible. This result generalizes the analogous result which is known for level 1 context-free processes. We show that this result holds also in the case of backward reachability analysis under a regular constraint on configurations. As a corollary, we obtain a symbolic model checking algorithm for the temporal logic E(U,X) with regular atomic predicates, i.e., the fragment of CTL restricted to the EU and EX modalities.

Affiliated with

Also associated with

No associations

Rating

Symbolic Reachability Analysis of Higher-Order Context-Free Processes 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 Reachability Analysis of Higher-Order Context-Free Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symbolic Reachability Analysis of Higher-Order Context-Free Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-447742