This paper addresses the problem of correcting spelling errors that result in valid, though unintended words (such as peace and piece, or quiet and quite) and also the problem of correcting particular word usage errors (such as amount and number, or among and between). Such corrections require contextual information and are not handled by conventional spelling programs such as Unix spell. First, we introduce a method called Trigrams that uses part-of-speech trigrams to encode the context. This method uses a small number of parameters compared to previous methods based on word trigrams. However, it is effectively unable to distinguish among words that have the same part of speech. For this case, an alternative feature-based method called Bayes performs better; but Bayes is less effective than Trigrams when the distinction among words depends on syntactic constraints. A hybrid method called Tribayes is then introduced that combines the best of the previous two methods. The improvement in performance of Tribayes over its components is verified experimentally. Tribayes is also compared with the grammar checker in Microsoft Word, and is found to have substantially higher performance.

This paper presents an algorithm (a parser) for analyzing sentences according to grammatical constraints expressed in the framework of lexicalized tree‐adjoining grammar. For the current grammars of English, the algorithm behaves much better and requires much less time than its worst‐case complexity. The main objective of this work is to design a practical parser whose average‐case complexity is much superior to its worst case. Most of the previous methods always required the worst‐case complexity. The algorithm can be used in two modes. As a recognizer it outputs whether the input sentence is grammatically correct or not. As a parser it outputs a detailed analysis of the grammatically correct sentences. As sentences are read from left to right, information about possible continuations of the sentence is computed. In this sense, the algorithm is called a predictive left to right parser. This feature reduces the average time required to process a given sentence. In the worst case, the parser requires an amount of time proportional to G2n6 for a sentence of n words and for a lexicalized tree‐adjoining grammar of size G. The worst‐case complexity is only reached with pathological (not naturally occurring) grammars and inputs.

Lexicalized context-free grammar (LCFG) is an attractive compromise between the parsing efficiency of context-free grammar (CFC) and the elegance and lexical sensitivity of lexicalized treeadjoining grammar (LTAG).LCFC is a restricted form of LTAG that can only generate contextfree languages and can be parsed in cubic time.However, LCF(I supports much of the elegance of LTAG's analysis of English and shares with LTAG the ability to lexicalize CF(I;s without changing the trees generated. MotivationContext-free grammar (CFG) has been a well accepted framework for computational linguistics for a long time.While it has drawbacks, including the inability to express some linguistic constructions, it has the virtue of being computationally efficient, O(n3)-time in the worst case.Recently there has been a gain in interest in the so-called 'mildly' context-sensitive formalisms (Vijay-Shanker, 1987;Weir, 1988;Joshi, Vijay-Shanker, and Weir, 1991; Vijay-Shanker and Weir, 1993a) that generate only a small superset of context-free languages.One such formalism is lexicalized tree-adjoining grammar (LTAG) (Schabes, Abeill~, and Joshi, 1988; Abeillfi et al., 1990;Joshi and Schabes, 1992), which provides a number of attractive properties at the cost of decreased efficiency, O(n6)-time in the worst case (Vijay-Shanker, 1987;Schabes, 1991;Lang, 1990;Vijay-Shanker and Weir, 1993b).

The inside-outside algorithm for inferring the parameters of a stochastic context-free grammar is extended to take advantage of constituent information (constituent bracketing) in a partially parsed corpus.Experiments on formal and natural language parsed corpora show that the new algorithm can achieve faster convergence and better modeling of hierarchical structure than the original one.In particular, over 90% test set bracketing accuracy was achieved for grammars inferred by our algorithm from a training set of handparsed part-of-speech strings for sentences in the Air Travel Information System spoken language corpus.Finally, the new algorithm has better time complexity than the original one when sufficient bracketing is provided.

The precise formulation of derivation for tree-adjoining grammars has important ramifications for a wide variety of uses of the formalism, from syntactic analysis to semantic interpretation and statistical language modeling. We argue that the definition of tree-adjoining derivation must be reformulated in order to manifest the proper linguistic dependencies in derivations. The particular proposal is both precisely characterizable, through a compilation to linear indexed grammars, and computationally operational, by virtue of an efficient algorithm for recognition and parsing.

We introduce an algorithm for designing a predictive left to right shift-reduce non-determinisic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The performance of the resulting parser is formally proven to be superior to Earley's parser (1970).The technique employed consists in constructing before run-time a parsing table that encodes a non-deterministic machine in the which the predictive behavior has been compiled out. At run time, the machine is driven in pseudo-parallel with the help of a chart.The recognizer behaves in the worst case in O(|G|2n3)-time and O(|G|n2)-space. However in practice it is always superior to Earley's parser since the prediction steps have been compiled before run-time.Finally, we explain how other more efficient variants of the basic parser can be obtained by determinizing portions of the basic non-deterministic push-down machine while still using the same pseudo-parallel driver.

We define a set of deterministic bottom-up left to right parsers which analyze a subset of Tree Adjoining Languages. The LR parsing strategy for Context Free Grammars is extended to Tree Adjoining Grammars (TAGs). We use a machine, called Bottom-up Embedded Push Down Automation (BEPDA), that recognizes in a bottom-up fashion the set of Tree Adjoining Languages (and exactly this set). Each parser consists of a finite state control that drives the moves of a Bottom-up Embedded Pushdown Automaton. The parsers handle deterministically some context-sensitive Tree Adjoining Languages. In this paper, we informally describe the BEPDA then given a parsing table, we explain the LR parsing algorithm. We then show how to construct an LR(0) parsing table (no lookahead). An example of a context-sensitive language recognized deterministically is given. Then, we explain informally the construction of SLR(1) parsing tables for BEPDA. We conclude with a discussion of our parsing method and current work.

We will describe an Earley-type parser for Tree Adjoining Grammars (TAGs). Although a CKY-type parser for TAGs has been developed earlier (Vijay-Shanker and Joshi, 1985), this is the first practical parser for TAGs because as is well known for CFGs, the average behavior of Earley-type parsers is superior to that of CKY-type parsers. The core of the algorithm is described. Then we discuss modifications of the parsing algorithm that can parse extensions of TAGs such as constraints on adjunction, substitution, and feature structures for TAGs. We show how with the use of substitution in TAGs the system is able to parse directly CFGs and TAGs. The system parses unification formalisms that have a CFG skeleton and also those with a TAG skeleton. Thus it also allows us to embed the essential aspects of PATR-II.