Sculptures in Concurrency
We give a formalization of Pratt's intuitive sculpting process for higher-dimensional automata (HDA). Based on this, we show that sculptures, Pratt's Chu spaces, and Johansen's ST-structures are in close correspondence. We also develop an algorithm to decide whether a HDA can be sculpted and use this to show that some natural acyclic HDA are not sculptures. We believe that this contradicts Pratt's intuition that sculpting suffices for modeling of concurrent behavior. We also show that there are sculptures whose unfoldings cannot be sculpted, and that sculptures are the same as Euclidean cubical complexes. This exposes a close connection between geometric and combinatorial models for concurrency which may be of use for both areas.
READ FULL TEXT