Finite-state concurrent programs can be expressed pairwise

Details Finite-state concurrent programs can be expressed pairwise Finite-state concurrent programs can be expressed pairwise

2008-01-04

arxiv.org/abs/0801.0677v1

Computer Science

Logic in Computer Science

14 pages

Scientific paper

We present a \emph{pairwise normal form} for finite-state shared memory concurrent programs: all variables are shared between exactly two processes, and the guards on transitions are conjunctions of conditions over this pairwise shared state. This representation has been used to efficiently (in polynomial time) synthesize and model-check correctness properties of concurrent programs. Our main result is that any finite state concurrent program can be transformed into pairwise normal form. Specifically, if $Q$ is an arbitrary finite-state shared memory concurrent program, then there exists a finite-state shared memory concurrent program $P$ expressed in pairwise normal form such that $P$ is strongly bisimilar to $Q$. Our result is constructive: we give an algorithm for producing $P$, given $Q$.

Affiliated with

Also associated with

No associations

Rating

Finite-state concurrent programs can be expressed pairwise 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 Finite-state concurrent programs can be expressed pairwise, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite-state concurrent programs can be expressed pairwise will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-379673