I've started to read about process calculi (such as CSP and π-calculus). It seems to me that they are extremely general and can represent pretty much any concurrent system, many of which will be unable to "make progress".

I wondered if there were much more restrictive formalisms for describing concurrent processes? Perhaps something close to formal languages augmented with a parallel composition (a kind of tensor product of the joined languages) might work quite well? Maybe, in particular a Parsing expression grammar.

Process calculi seem to generally have a concept of channels on which synchronous messages are exchanged. The set of allowable messages are known as the alphabet of a process, and it seems analogous to the symbol set of a formal language (you'd need to augment the symbols with a send and a receive label).

The possible traces of a process calculus would be analogous to the possible strings of a language.

So, the actual questions: is there something like this in the research literature? Thanks!

  • 4
    $\begingroup$ There are many typing systems for process caluculi -- session types being the most well-known example. Is this not what you have in mind? $\endgroup$ Jul 11, 2017 at 9:14
  • $\begingroup$ Thank you. I'm not sure, but it looks interesting – I'll have a read! $\endgroup$
    – Benjohn
    Jul 11, 2017 at 9:20
  • $\begingroup$ This definitely looks like an interesting avenue, thank you. I'm particularly interested in interactive GUI applications. I think current formalisms are lacking in this area. Session Types seem to have developed from concurrent network protocols, but perhaps the approach could also benefit GUI. $\endgroup$
    – Benjohn
    Jul 11, 2017 at 11:33
  • 2
    $\begingroup$ Yes, the technology also works for interactive GUI applications, see work on session types for event-driven programming like this. But see also The Essence of Event-Driven Programming. $\endgroup$ Jul 11, 2017 at 11:40

1 Answer 1


I wondered if there were much more restrictive formalisms for describing concurrent processes?

Petri nets are IMO more restrictive than the process calculus and such. They are state-transition systems, which are pretty much like formal grammars (like parsing expression grammars). They all boil down to states and rules / transitions. Petri nets include parallel composition.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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