This article focuses on the relevance of computational complexity for cognition. The syntactic items may be expressions that are surface strings. But in general, strings are syntactically ambiguous in that they can be generated in more than one way from atomic expressions and operations. The semantic function must take disambiguated items as arguments. When expressions are ambiguous, expressions cannot be the arguments. Instead, it is common to take the arguments to be terms, whose surface syntax reflects the derivation of the (...) string. The semantic function differs in one other important respect from an arithmetic function, since it maps entities between domains, from a syntactic to an ontic or conceptual domain of meanings. Compositionality helps to explain the rate of success in linguistic communication when the sentence used or the content communicated is new. (shrink)

Starting from the familiar observation that no straightforward treatment of pure quotation can be compositional in the standard (homomorphism) sense, we introduce general compositionality, which can be described as compositionality that takes linguistic context into account. A formal notion of linguistic context type is developed, allowing the context type of a complex expression to be distinct from those of its constituents. We formulate natural conditions under which an ordinary meaning assignment can be non-trivially extended to one that is sensitive to (...) context types and satisfies general compositionality. As our main example we work out a Fregean treatment of pure quotation, but we also indicate that the method applies to other kinds of context, e.g. intensional contexts. (shrink)

There have been, I am afraid, almost as many answers to the question what is logic? as there have been logicians. However, if logic is not to be an obscure "science of everything", we must assume that the majority of the various answers share a common core which does offer a reasonable delimitation of the subject matter of logic. To probe this core, let us start from the answer given by Gottlob Frege (1918/9), the person probably most responsible for modern (...) logic: the subject matter of logic is "truth", and especially its "laws"1. How should we understand the concept of "laws of truth"? The underlying point clearly is that the truth/falsity of our statements is partly a contingent and partly a necessary, lawful matter: that "Paris is in France" is true is a contingent matter, whereas that "Paris is in France or it is not in France" is true is a necessary matter (let us, for the time being, leave aside the Quinean scruples regarding the delimitation of necessarily true statements). Logic,then, should focus on the statements that are true as a matter of law (i.e. necessarily), or, more generally, the truth of which "lawfully depends" on some other statements (i.e. which are true as a matter of law provided these other statements are true). This renders Fregean laws of truth as, in general, a matter of "lawful truth-dependence" - i.e. of entailment or inference (again, let us now disregard any possible difference between these two concepts). This yields a conception of logic as a theory of entailment or inference, a conception which looms behind many other specifications of the subject matter of logic and which, I think, is ultimately correct. However, we can also see the logician – and this is the view we will stick to here – as trying to separate true sentences from false ones; or, equivalently, to map sentences onto truth and falsity. Let us first consider the case of a non-empirical language with a single, definite truth valuation – like the language of Peano arithmetic.. (shrink)

with the meaning function [[·]] appearing on both sides. (1) is commonly construed as a prescription for computing the meaning of a based on the parts of a and their mode of combination. As equality is symmetric, however, we can also read (1) from right to left, as a constraint on the meaning [[b]] of a term b that brings in the wider context where b may occur, in accordance with what Dag Westerst˚ahl has recently described as “one version of (...) Frege’s famous Context Principle”. (shrink)

This paper starts from the observation that the standard arguments for compositionality are really arguments for the computability of semantics. Since computability does not entail compositionality, the question of what justifies compositionality recurs. The paper then elaborates on the idea of recursive semantics as corresponding to computable semantics. It is then shown by means of time complexity theory and with the use of term rewriting as systems of semantic computation, that syntactically unrestricted, noncompositional recursive semantics leads to computational explosion (factorial (...) complexity). Hence, with combinatorially unrestricted syntax, semantics with tractable time complexity is compositional. (shrink)

The goal of inquiry in this essay is to ascertain to what extent the Principle of Compositionality – the thesis that the meaning of a complex expression is determined by the meaning of its parts and its mode of composition – can be justifiably imposed as a constraint on semantic theories, and thereby provide information about what meanings are. Apart from the introduction and the concluding chapter the thesis is divided into five chapters addressing different questions pertaining to the overarching (...) goal of inquiry. Chapter Two is an attempt to determine whether the Principle of Compositionality is a trivial principle. It is argued that this is not the case in the context of providing the semantics of natural languages since it is an open question whether the best theories that respect available syntactic and semantic data are compositional. Chapter Three and Chapter Four ask whether there are reasons to think that the Principle of Compositionality is true. It is argued that the three most commonly cited reasons for thinking that correct semantic theories must be compositional – Linguistic Creativity, Productivity and Systematicity – in fact only give us reasons to think that the meaning of complex expressions depend on the meanings of their parts and their modes of composition, but not that the meaning of complex expressions depend ONLY on those factors. Chapter Five asks whether there are any reasons to think that the Principle of Compositionality is false. It is argued that all the phenomena that have been suggested entail non-compositionality are in fact compatible with some versions of compositionality. Even if this conclusion is reached in this chapter, the conclusion of the previous two chapters entails that we are not justified in imposing the Principle of Compositionality as an adequacy constraint on Semantic theories. Chapter Six explores the ways in which information about what meanings are can be derived by imposing constraints on semantic theories. It is argued that the distinction emphasized in Chapter Three and Chapter Four between depending on and depending ONLY on is of critical importance. It is demonstrated that the informative potential of the Principle of Compositionality goes far beyond that of the principle we are in fact justified in imposing on semantic theories. So not only is it the case that we cannot learn anything about meanings from the justified imposition of the Principle of Compositionality – since we cannot justifiably impose it as a constraint on semantic theories – what we could have learned from it had we been justified in imposing it is very different from what we can learn from the principle that we are justified in imposing. (shrink)