SEQUITUR is an algorithm that infers a hierarchical structure from a sequence
of discrete symbols by replacing repeated phrases with a grammatical rule that
generates the phrase, and continuing this process recursively. The result is a
hierarchical representation of the original sequence, which offers insights
into its lexical structure. The algorithm is driven by two constraints that
reduce the size of the grammar, and produce structure as a by-product. SEQUITUR
breaks new ground by operating incrementally. Moreover, the method's simple
structure permits a proof that it operates in space and time that is linear in
the size of the input. Our implementation can process 50,000 symbols per second
and has been applied to an extensive range of real world sequences.

SEQUITUR 是一种通过用语法规则替代重复短语来推断符号序列中的分层结构，具有线性时间和空间开销的算法，可应用于各种实际序列数据。

在序列中识别层次结构：一种线性时间算法

Identifying Hierarchical Structure in Sequences: A linear-time algorithm

We prove a theorem stating that any semantics can be encoded as a
compositional semantics, which means that, essentially, the standard definition
of compositionality is formally vacuous. We then show that when compositional
semantics is required to be "systematic" (that is, the meaning function cannot
be arbitrary, but must belong to some class), it is possible to distinguish
between compositional and non-compositional semantics. As a result, we believe
that the paper clarifies the concept of compositionality and opens a
possibility of making systematic formal comparisons of different systems of
grammars.

我们证明一个定理，即任何语义都可以被编码为组合语义，这意味着，本质上，组合性的标准定义是形式上的空洞。我们随后证明，当要求组合语义是 “系统化” 的（即意义函数不能是任意的，而必须属于某个类别），就可以区分组合性和非组合性语义。因此，我们相信这篇论文阐明了组合性的概念，并开辟了对不同语法系统进行系统形式比较的可能性。

从构成语义到系统语义

From compositional to systematic semantics

Gemini is a natural language understanding system developed for spoken
language applications. The paper describes the architecture of Gemini, paying
particular attention to resolving the tension between robustness and
overgeneration. Gemini features a broad-coverage unification-based grammar of
English, fully interleaved syntactic and semantic processing in an all-paths,
bottom-up parser, and an utterance-level parser to find interpretations of
sentences that might not be analyzable as complete sentences. Gemini also
includes novel components for recognizing and correcting grammatical
disfluencies, and for doing parse preferences. This paper presents a
component-by-component view of Gemini, providing detailed relevant measurements
of size, efficiency, and performance.

Gemini 是一种自然语言理解系统，它采用广覆盖的在英语上的基于统一的语法，在所有路径、自底向上的解析器中进行完全交错的语法和语义处理，并包括识别和纠正语法发生抖动的新颖组件和做解析首选项的组件。