November – 2007 ^December

Text remains the main medium to convey information and knowledge. Machine-readable text has become plentiful and accessible through search engines. Many applications are concerned with transforming text from one to another. The field that studies such transformation is called text to text generation (T2T). T2T is a sub-field of natural language generation (NLG), and stands in contrast with data to text (D2T) generation (where the input data is any non-textual representation).

In T2T, textual units (sentences, clauses, phrases) are extracted from one context and recombined into a new text. As in NLG in general, one can split the overall task of generation into several steps:

• Content selection
• Content organization
• Realization: the rendering of the selected content into fluent language.

In T2T, "content" is encoded as textual units - generally called "SCU" (Shared Content Unit). The input to a T2T system includes a collection of texts that are related in topic, for example a collection of news reports describing the same event (from different sources or published at different times). Content selection and organization in D2T applications is generally related to knowledge representation and inferencing. In the case of T2T, it is related to Information Extraction, which includes named entity recognition, coreference resolution, entity identification, relation identification and scenario identification.

Realization is the linguistic component of generation, and is organized around the following steps:

• Lexicalization (selection of the words)
• Aggregation
• Referring expression generation
• Rhetorical structuring and ordering
• Centering and salience
• Syntactic realization (ordering of the words, morphological inflection)

In the lecture, I will review sample T2T applications and the corresponding methods. I will focus on the type of knowledge required to perform T2T and how it can be acquired. I will end with a review of open issues and possible topics for further research.

For a function g from natural numbers to natural numbers, a g-regressive coloring of pairs of natural numbers is a coloring C satisfying $C(m,n) \le g(\min{m,n})$ for all $m,n$.

The g-regressive Ramsey number of k is the least N so that for every g-regressive coloring C there exists a subset H of of size at least k which is min-homogeneous for C, namely, the color $C(m,n)$ of a pair ${m,n}$ of H depends only on $\min(m,n)$.

We compute a sharp threshold on g at which g-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian. We prove:

Suppose g is nondecreasing and unbounded. Then the g-regressive Ramsey number is bounded by some primitive recursive function in k if and only if for every $t>0$ there is some $M(t)$ so that for all $n \ge M(t)$, $g(n) < n^{1/t}$ and $M(t)$ is primitive recursive in t.

We also give an extremely large lower bound on the identity-regressive Ramsey number of k=82. Joint work with Menachem Kojman, Gyesik Lee and Andreas Weiermann.

A function is Turing computable if it can be specified by a Turing machine. Turing's definition [1936] of a function, computable by a Turing machine, was followed in his dissertation [1939], in which he defined the notion of a set $A$ being computable relative to a set $B$. We then say $A$ is Turing reducible to $B$ ($A\leq_T B$). We identify a degree as an equivalence class of sets of natural numbers, each reducible to the other

The least degree is the set of all recursive subsets of $\omega$, denoted $\deg{0}$. A degree $\deg{b}$ is minimal if $\deg{b}>\deg{0}$ and there is no $\deg{c}$ such that $\deg{0}<\deg{c}<\deg{b}$. That is, it is minimal in the ordering of degrees. I will present Spector's result [1956]: There is a minimal degree. It follows that the ordering $\leq$ on $\D$ (the structure of the degrees) is not dense. This result proved to be useful in many embedability results as well as other results concerning the structure of $\D$.