nLab
compositionality

Idea

Compositionality describes how complex things can be assembled out of simpler parts. It is sometimes called Frege’s principle after Gottlob Frege, although it was arguably assumed by George Boole decades before Frege’s work.

In computation

From 1:

The compositional description of complex objects is a fundamental feature of the logical structure of computation. The use of logical languages in database theory and in algorithmic and finite model theory provides a basic level of compositionality, but establishing systematic relationships between compositional descriptions and complexity remains elusive. Compositional models of probabilistic systems and languages have been developed, but inferring probabilistic properties of systems in a compositional fashion is an important challenge. In quantum computation, the phenomenon of entanglement poses a challenge at a fundamental level to the scope of compositional descriptions. At the same time, compositionally has been proposed as a fundamental principle for the development of physical theories.

In linguistics

References

  1. Compositionality is the name of a workshop hosted at UC Berkeley in 2016. Accessed online at https://simons.berkeley.edu/workshops/logic2016-3.

  2. Compositionality is also the name of a journal whose aim is to publish papers in this area.

Last revised on August 30, 2019 at 06:11:01. See the history of this page for a list of all contributions to it.