3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Dave Clarke Feb 13 '13 at 10:47
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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