5
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • 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$
    – Martin Berger
    Commented Jul 11, 2017 at 9:14
  • $\begingroup$ Thank you. I'm not sure, but it looks interesting – I'll have a read! $\endgroup$
    – Benjohn
    Commented 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
    Commented 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$
    – Martin Berger
    Commented Jul 11, 2017 at 11:40

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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