Some New Directions for ACP Research

This paper at lists some new directions for research related to the Algebra of Communicating Processes (ACP). Most of these directions have been inspired by work on SubScript, an ACP based extension to the programming language Scala. SubScript applies several new ideas that build on ACP, but currently these lack formal treatment. Some of these new ideas are rather fundamental. E.g. it appears that the theory of ACP may well apply to structures of any kind of items, rather than to just processes. The aim of this list is to raise awareness of the research community about these new ideas; this could help both the research area and the programming language SubScript.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

re "well apply to structures of any kind of items"

What kinds of structures?

I mean data structures

The linked paper presented a GUI controller as an example program. I quote the following section:

2.1 Algebra of Items
In the previous example, buttons, key codes and event codes were added:

searchCommand = searchButton + Key.Enter
cancelCommand = cancelButton + Key.Escape
exitCommand = exitButton + windowClosing

Thanks to Scala’s implicit mechanism we can glue any kind of items together using the ACP operators. The result is an algebra of general items rather than just of processes. A transformation may turn such an item specification to a process specification. In the above, the obvious transformation are about receiving input. It is also possible to do the opposite: the specification may for instance instruct a test robot to generate button clicks etc.

A particular application of such algebra’s of items is in language grammars: these are descriptions of certain text structures, rather than processes that accept or produce such texts.

The paper "Equivalence notions for concurrent systems and refinement of actions" [9] already covers some technical issues of such a generalization to an algebra of items.
[9] R. van Glabbeek and U. Goltz. Equivalence notions for concurrent systems and refinement of actions. In A. Kreczmar and G. Mirkowska, editors, Mathematical Foundations of Computer Science 1989, volume 379 of Lecture Notes in Computer Science, pages 237–248. Springer Berlin Heidelberg, 1989.

re I mean data structure

Yeah, I think I more or less get that.

The question I'm trying to ask is a little bit vague but is basically:

What mathematical structures do these data structures have in common? How does the range of mathematical structures possible relate to process composition structures?

The process algebra itself is, of course, one mathematical structure the data structures and process compositions have in common (which is your point).

I'm wondering if there are other interesting relations.

For a example, a computationally incomplete process algebra might be regular in the sense that it's expressions specify possible event traces that, if we write down the list of events, we see sentences in a particular regular language. Such a process algebra would also be an algebra for regular languages. If the same process algebra is used to describe data structures, somehow, presumably those data structures would be regular in some sense that might be explainable and interesting.

Models of Computation: Automata and Processes

@Thomas: I recommend the syllabus of the course "Automata & Process Theory" for bachelor students Computer Science (at least in the year 2010), at Eindhoven University of Technology.

A related view of data structures is The algebra (and calculus!) of algebraic data types.
See also the discussion on Reddit and this presentation by John Pretty.