Complexity as a basis for comparing semantic models of concurrency

We investigate some aspects of interexpressiveness of languages and their (denotational) semantic models by viewing semantic functions from a complexity-theory viewpoint. We classify semantic functions as polynomial or finite if a language term of size n produces a meta-language object respectively polynomially bounded in n or finite. Languages involving concurrency manifest most interest which we associate to the fact that their semantic models in general lack λ-style abstraction. The paper provides a quantifiable reason why labelled event structures form a more reasonable model for the choice and concurrency operators of CCS than do synchronisation trees. Similarly we show the representation of conflict by places within (at least occurrence forms of) Petri-nets is exponentially larger than the relational representation within corresponding event structures. An application is a criterion for selection of semantic models for real-world algorithmic purposes; for example, ‘model checking’ algorithms which use an exponentially larger semantic representation of programs are unlikely to be efficient