Peter Pagin

Interpretational Complexity

The Principle of Compositionality says:

(CP) The meaning of a complex expression is a function of the meanings of its parts and its mode of composition.

It is often assumed by philosophers and linguists that (CP) is true of natural languages. The principle is natural, and has deep historical roots. How should it be justified?

The standard arguments use the premise that we can work out the meaning of linguistic expressions that we haven't heard before. A problem with these arguments is that linguistic meaning may be computable without being compositional. We need new considerations to motivate compositionality over and above computability.

The current proposal is to seek the justification in the study of the complexity of semantic interpretation: how many cognitive steps do I need to take to interpret a new expression, in relation to the size of the expression? The complexity must be low, since we have limited cognitive resources and yet interpret both reliably and fast. The hypothesis is that if the interpretational complexity of a semantics is low, then it is compositional.

Earlier work (Pagin 2011), where I used methods from Computer Science, indicate that this is in fact the case. But these results were only partial and are in need of completion in several respects, e.g. by considering more complex languages, and by investigating the relevance of computational complexity to cognitive difficulty. This completion is the purpose of the project.

Peter Pagin, Philosophy, Stockholm University


The purpose of the project was to reach a better understanding of the relation between semantics on the one hand and the complexity of interpretation on the other, in a number of different respects. Another purpose, if there was time, was to reach a better understanding of the relation between pragmatics and interpretational complexity. The purpose has not changed during the project, except insofar as more time than originally planned was devoted to interpretational principles within systematic pragmatics. There I have developed a theory about coherence raising as an engine for so-called pragmatic enrichment. This development has resulted, so far, in one published article and two (commissioned) papers, one currently forthcoming and one under review.

  Most important results

The three most important results are technical.

1. Determination of the complexity of the interpretation of quantifier languages. I show in Pagin 2012 that the interpretation of free variables, generated by quantifiers, increases the general interpretational complexity, and that this complexity nevertheless is comparatively low: quadratic (the number of steps in the interpretation process is less than the square of the size of the expression).

2. The complexity of recursive semantics. I show in Pagin 2016c that the interpretational complexity for recursive but non-compositional semantics is intractable: it is higher than exponential (the number of steps is higher than an exponential function of the size of the expression).

These two results show that low interpretational complexity implies compositionality, which also was the hypothesis of the project. In turn, this shows that the theory that natural languages have a compositional semantics does have a theoretical justification from the consideration of interpretational complexity.

3. In three papers on so-called pragmatic enrichment, I show that this is a phenomenon that to a large extent can be predicted from principles of so-called coherence raising: we read more into an utterance than what is explicitly said when this leads to an increase of coherence between different parts of the content. I show in one paper how these principles relate to semantic properties of quantifiers, and in another how they relate to the principle that in interpretation we should strive to maximize truth (The Principle of Charity).

One result is the that the interpretational complexity does not increase, because truth after the enrichment entails truth before the enrichment. That is, the interpretation that results from applying the Principle of Charity does not become more complex, since enrichment does not lead from a false proposition to a true one.

  New research questions

1. In their book Why Only Us?, MIT 2016, Robert Berwick and Noam Chomsky have argued that certain phenomena within syntax show that language primarily exists for the sake of thinking, not for the sake of communicating. The phenomena in question are so-called movements: a syntactic element is moved from one place in deep structure to another place in surface structure. The idea is that this increases the difficulty for the receiver's interpretation, and that in turn shows that language primarily is a tool for thinking. The tendency of my work has been the opposite: compositionality decreases the difficulty for the receiver. In part, this can be used as a direct counterargument against Berwick and Chomsky. In part, the clash opens a new research question that I have started looking into, the question how the syntactic and semantic phenomena, and their associated complexity measures, relate to each other. In an upcoming key-note at The Fifth International Conference on Philosophy of Language and Linguistics, Lodz, Poland, in May 2017, I intend to discuss these issues.

2. I have recently learned that it is a consequence of so-called Prototype Theory that the complexity of categorization dramatically increases, and in fact becomes intractable. This has a direct effect on the semantics for vague expressions (like 'bald' and 'heap'), and this in turn relate questions of interpretational complexity to my theory of vagueness. This is a new research question.

  International integration
The contributions from the project are integrated in the forefront of research as regards compositionality, as regards pragmatic enrichment, and as regards coherence theory. Some of the contributions make use of two established subjects within Computer Science, Complexity Theory and Term Rewriting Theory. It also relates to recent results about the connection between them. The contributions are also related to recent research in the complexity of syntax as well as to questions of complexity in other parts of semantics. This latter holds in particular of the theory of Generalized Quantifiers and their complexity issues. The research into the complexity of semantic interpretation (comprehension) is, however, original with the present project.

Contributions outside the scientific community
There is nothing in particular to mention here, except possibly my contribution to the handbook A Companion to Donald Davidson, Wiley 2013, eidted by Kirk Ludwig and Ernie Lepore, where I mention the problem of the relation between radical interpretation and the justification of compositionality, which is one aspect of a question that has been central in the project.

The two most important publications
The two most important papers of the project are still unpublished. Those are Pagin 2016c and Pagin 2017. The former shows that compositionality is a necessary condition for tractable interpretational complexity. Several important results are achieved along the way. I give a general definition of the idea of semantically recursive functions and show that, given a gödel coding of a syntactic domain and a meaning domain, and with the Church-Turing Thesis as a premise, computable semantic functions are semantically recursive. I also show how to apply Term Rewriting Theory generally for implementing semantics and that such term rewriting systems have the properties required for computing functions.

The second paper give a (virtually) comprehensive overview of the arguments for the truth of the the principle of compositionality that are intuitively plausible and have been proposed in the literature. I show that the main current arguments are inconclusive. In some cases, they fail because of relying on assumptions that are too strong to provide justification. In some cases, the principle of compositionality is not supported by the premises. In particular, semantic computability does not imply compositionality. I show that the argument from communication does provide a justification of compositionality, but only if complexity aspects are taken into account.

Among the papers that are already published, I would emphasize Pagin 2012 and Pagin 2014. In the former, in the context of a discussion of the philosophy of language of Donald Davidson, I discuss the general relation between competence and performance from the perspective of computational complexity. I also show that a language that contains variable-binding operators, such as quantifiers, and that allows such operators to be embedded under others, have a higher complexity, more precisely quadratic, because of a technicality that concerns the pairing of (a representation of) the assignment function with free variables.

In the latter, I show how a certain type of pragmatic operations, so-called pragmatic enrichment, can be given a systematic account that provides the possibility of predicting the phenomenon. An example (from Robyn Carston) is "He ran to the edge of the cliff and jumped", which in interpretation is enriched into "He ran to the edge of the cliff and jumped over the edge of the cliff". Partly building on extant theory of coherence relations (Andrew Kehler), I show that the standard examples of enrichment in the literature can be explained by the fact to they lead from a lower to a higher degree on the coherence scale.

Both of these works fit into a general strategy for explaining what linguistic meaning is that makes appeal to the contribution of semantic theories for explaining successful linguistic communication. In the latter case, pragmatics would constitute an obstacle to such an explanation unless pragmatics itself can be shown to be systematic.

  Publication strategy
The main strategy is to publish work in highly ranked international journals or in centrally published collections. This goal is reached in almost all the published work listed below. Exceptions are made when I have accepted invitations to publishing in less highly ranked journals that merit support (for instance the Italian journal Argumenta in the case of Pagin 2016e).

All publication will be freely accessible on the internet. Either they are published with open access to begin with (such as Pagin 2013 and Pagin 2016a) or preprints will be made available, at first on my homepage at the Department of Philosophy, Stockholm University, and then at the DIVA repository at Stockholm University.

The link to my homepage is:


Pagin, Peter (2012). ‘Truth-theories, Competence, and Semantic Computation’. In: Davidson’s Philosophy: A Reappraisal. Ed. by Gerhard Preyer. Oxford: Oxford University Press.

— (2013). ‘Compositionality, Complexity, and Evolution’. In: Proceedings from a Symposium on Language Acquisition and Language Evolution. Ed. by Francisco Lacerda. PERILUS. Stockholm University, Department of Linguistics. URL:

— (2014). ‘Pragmatic Enrichment as Coherence Raising’. In: Philosophical Studies 168, pp. 59–100.

— (2016a).‘A General Argument Against Structured Propositions’. In:Synthese, Online. DOI: 10.1007/s11229-016-1244-4.

— (2016b). ‘Belief sentences and compositionality’. Draft.

— (2016c). ‘Compositionality, Computability,and Complexity’. Draft.

— (2016d). ‘Enrichment, Coherence, and Quantifier Properties’. Submitted.

— (2016e). ‘Radical interpretation and Pragmatic Enrichment’. Forthcoming in Argumenta.

— (2017). ‘How [Not] To Justify Compositionality’. Draft.