Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reading on concurrent processes and algorithms which find infinite processes by searching the process graph recursively.

Most of the material I have found is not for beginners. I am looking for references / algorithms that can help me understand:

  1. What are process graphs?
  2. How to search for infinite processes in these graphs?

Thanks in advance

share|cite|improve this question
You could cite some of the material you are reading. This would help us find an answer to your question. Also, more details might help. – Dave Clarke Feb 13 '13 at 10:47
up vote 2 down vote accepted

As you propably know, a process (in terms of process algebra like CSP) can consume an input and will the behave like another process (unless it is a process that does not accept input, usually called STOP).

You can construct a graph where the nodes are the processes and the outgoing edges the input that the node can consume, directed to the node (process) that gives the new behaivior. If such a graph contains a directed path back to a starting node (i.e., a circle), you have an infinite process.

Finding a circle in a graph is a standard problem in graph theory and is usually done by DFS.

A good introduction to CSP is Tony Hoare's Book on that subject, what is easy to read also for beginners. (However, Hoare does not use the term "process graph" but talks only on "graphs".) The standard text book for CCS is Milner's "Communication and Concurrency" published by Prentice Hall.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.