Combinatory categorial grammar

Combinatory categorial grammar (CCG) is an efficiently parseable, yet linguistically expressive grammar formalism. It has a transparent interface between surface syntax and underlying semantic representation, including predicateargument structure, quantification and information structure.
CCG relies on combinatory logic, which has the same expressive power as the lambda calculus, but builds its expressions differently. The first linguistic and psycholinguistic arguments for basing the grammar on combinators were put forth by Steedman and Szabolcsi. More recent prominent proponents of the approach are Jacobson and Baldridge.
For example, the combinator B (the compositor) is useful in creating longdistance dependencies, as in "Who do you think Mary is talking about?" and the combinator W (the duplicator) is useful as the lexical interpretation of reflexive pronouns, as in "Mary talks about herself". Together with I (the identity mapping) and C (the permutator) these form a set of primitive, noninterdefinable combinators. Jacobson interprets personal pronouns as the combinator I, and their binding is aided by a complex combinator Z, as in "Mary lost her way". Z is definable using W and B.
Contents
Parts of the Formalism
The CCG formalism defines a number of combinators (application, composition, and typeraising being the most common). These operate on syntacticallytyped lexical items, by means of Natural deduction style proofs. The goal of the proof is to find some way of applying the combinators to a sequence of lexical items until no lexical item is unused in the proof. The resulting type after the proof is complete is the type of the whole expression. Thus, proving that some sequence of words is a sentence of some language amounts to proving that the words reduce to the type S.
Syntactic Types
The syntactic type of a lexical item can be either a primitive type, such as S, N, or NP, or complex, such as S\NP, or NP/N.
The complex types, schematizable as X/Y and X\Y, denote functor types that take an argument of type Y and return an object of type X. A forward slash denotes that the argument should appear to the right, while a backslash denotes that the argument should appear on the left. Any type can stand in for the X and Y here, making syntactic types in CCG a recursive type system.
Application Combinators
The application combinators, often denoted by > for forward application and < for backward application, apply a lexical item with a functor type to an argument with an appropriate type. The definition of application is given as:
Composition Combinators
The composition combinators, often denoted by B _{>} for forward composition and B _{<} for backward composition, are similar to function composition from mathematics, and can be defined as follows:
Typeraising Combinators
The typeraising combinators, often denoted as T _{>} for forward typeraising and T _{<} for backward typeraising, take argument types (usually primitive types) to functor types, which take as their argument the functors that, before typeraising, would have taken them as arguments.
Example
The sentence "the dog bit John" has a number of different possible proofs. Below are a few of them. The variety of proofs demonstrates the fact that in CCG, sentences don't have a single structure, as in other models of grammar.
Let the types of these lexical items be
We can perform the simplest proof (changing notation slightly for brevity) as:
Opting to typeraise and compose some, we could get a fully incremental, lefttoright proof:
Formal properties
CCGs are known to be able to generate the language . Examples of this are unfortunately too complicated to provide here, but can be found in VijayShanker and Weir (1994)^{[1]}.
Equivalencies
VijayShanker and Weir (1994)^{[1]} demonstrates that Linear Indexed Grammars, Combinatory Categorial Grammars, Treeadjoining Grammars, and Head Grammars are weakly equivalent formalisms, in that they all define the same string languages.
See also
References
 Baldridge, Jason (2002), "Lexically Specified Derivational Control in Combinatory Categorial Grammar." PhD Dissertation. Univ. of Edinburgh.
 Curry, Haskell B. and Richard Feys (1958), Combinatory Logic, Vol. 1. NorthHolland.
 Jacobson, Pauline (1999), “Towards a variablefree semantics.” Linguistics and Philosophy 22, 1999. 117–184
 Steedman, Mark (1987), “Combinatory grammars and parasitic gaps”. Natural Language and Linguistic Theory 5, 403–439.
 Steedman, Mark (1996), Surface Structure and Interpretation. The MIT Press.
 Steedman, Mark (2000), The Syntactic Process. The MIT Press.
 Szabolcsi, Anna (1989), "Bound variables in syntax (are there any?)." Semantics and Contextual Expression, ed. by Bartsch, van Benthem, and van Emde Boas. Foris, 294–318.
 Szabolcsi, Anna (1992), "Combinatory grammar and projection from the lexicon." Lexical Matters. CSLI Lecture Notes 24, ed. by Sag and Szabolcsi. Stanford, CSLI Publications. 241–269.
 Szabolcsi, Anna (2003), “Binding on the fly: Crosssentential anaphora in variablefree semantics”. Resource Sensitivity in Binding and Anaphora, ed. by Kruijff and Oehrle. Kluwer, 215–229.
Further reading
 Michael Moortgat, Categorial Type Logics, Chapter Two in J. van Benthem and A. ter Meulen (eds.) Handbook of Logic and Language. Elsevier, 1997, ISBN 0262220539
External links
 The Combinatory Categorial Grammar Site
 The ACL CCG wiki page (likely to be more uptodate than this one)
Categories: Grammar frameworks
 Combinatory logic
Wikimedia Foundation. 2010.
Look at other dictionaries:
Categorial grammar — is a term used for a family of formalisms in natural language syntax motivated by the principle of compositionality and organized according to the view that syntactic constituents should generally combine as functions or according to a function… … Wikipedia
Combinatory logic — Not to be confused with combinational logic, a topic in digital electronics. Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been… … Wikipedia
Minimalist grammar — Minimalist grammars are a class of formal grammars that aim to provide a more rigorous, usually proof theoretic, formalization of Chomskyan Minimalist program than is normally provided in the mainstream Minimalist literature. A variety of… … Wikipedia
Contextsensitive grammar — A context sensitive grammar (CSG) is a formal grammar in which the left hand sides and right hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context sensitive grammars are more general than… … Wikipedia
List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… … Wikipedia
Noam Chomsky — Chomsky redirects here. For other topics with the same name, see Chomsky (disambiguation). Noam Chomsky Noam Chomsky visiting Vancouver, Canada in 2004 … Wikipedia
CCG — is an acronym for:* Canadian Coast Guard * Castor Cracking Group * Centre for Computational Geography * Centre for Computational Geostatistics, [http://www.uofaweb.ualberta.ca/ccg/index.cfm (CCG)] * Chemical Computing Group, a pharmaceutical… … Wikipedia
epitomize — verb /əˈpɪt.əˌmaɪz/ a) To make an epitome of. The framework of Combinatory Categorial Grammar epitomizes the rule based generalized categorial architecture. b) To be an epitome of. Syn: sum up … Wiktionary
Grammaire contextuelle — Une grammaire contextuelle (en anglais context sensitive grammar) est une grammaire formelle dans laquelle les substitutions d un symbole non terminal sont soumises à la présence d un contexte gauche et d un contexte droit. Elles sont plus… … Wikipédia en Français
Mark Steedman — Mark Jerome Steedman, FBA, FRSE (born 18 September 1946) is a computational linguist and cognitive scientist. Steedman graduated from the University of Sussex in 1968, with a B.Sc in Experimental Psychology, and from the University of Edinburgh… … Wikipedia