Yves Schabes


1996

pdf
Combining Trigram-Based and Feature-Based Methods for Context-Sensitive Spelling Correction
Andrew Golding | Yves Schabes
34th Annual Meeting of the Association for Computational Linguistics

1995

pdf
Book Reviews: The Functional Treatment of Parsing
Yves Schabes
Computational Linguistics, Volume 21, Number 1, March 1995

pdf
Deterministic Part-Of-Speech Tagging With Finite State Transducers
Emmanuel Roche | Yves Schabes
Computational Linguistics, Volume 21, Number 2, June 1995

pdf bib
Tree Insertion Grammar: A Cubic-Time, Parsable Formalism that Lexicalizes Context-Free Grammar without Changing the Trees Produced
Yves Schabes | Richard C. Waters
Computational Linguistics, Volume 21, Number 4, December 1995

1994

pdf
An Alternative Conception of Tree-Adjoining Derivation
Yves Schabes | Stuart M. Shieber
Computational Linguistics, Volume 20, Number 1, March 1994

1993

pdf
Lexicalized Context-Fee Grammars
Yves Schabes | Richard C. Waters
31st Annual Meeting of the Association for Computational Linguistics

pdf
Stochastic Lexicalized Context-Free Grammar
Yves Schabes | Richard C. Waters
Proceedings of the Third International Workshop on Parsing Technologies

Stochastic lexicalized context-free grammar (SLCFG) is an attractive compromise between the parsing efficiency of stochastic context-free grammar (SCFG) and the lexical sensitivity of stochastic lexicalized tree-adjoining grammar (SLTAG) . SLCFG is a restricted form of SLTAG that can only generate context-free languages and can be parsed in cubic time. However, SLCFG retains the lexical sensitivity of SLTAG and is therefore a much better basis for capturing distributional information about words than SCFG.

pdf
Parsing the Wall Street Journal with the Inside-Outside Algorithm
Yves Schabes | Michal Roth | Randy Osborne
Sixth Conference of the European Chapter of the Association for Computational Linguistics

1992

pdf
Inside-Outside Reestimation From Partially Bracketed Corpora
Fernando Pereira | Yves Schabes
30th Annual Meeting of the Association for Computational Linguistics

pdf
An Alternative Conception of Tree-Adjoining Derivation
Yves Schabes | Stuart M. Shieber
30th Annual Meeting of the Association for Computational Linguistics

pdf
Inside-Outside Reestimation From Partially Bracketed Corpora
Fernando Pereira | Yves Schabes
Speech and Natural Language: Proceedings of a Workshop Held at Harriman, New York, February 23-26, 1992

pdf
Stochastic Tree-Adjoining Grammars
Yves Schabes
Speech and Natural Language: Proceedings of a Workshop Held at Harriman, New York, February 23-26, 1992

pdf
Structure Sharing in Lexicalized Tree-Adjoining Grammars
K. Vijay-Shanker | Yves Schabes
COLING 1992 Volume 1: The 14th International Conference on Computational Linguistics

pdf bib
Stochastic Lexicalized Tree-adjoining Grammars
Yves Schabes
COLING 1992 Volume 2: The 14th International Conference on Computational Linguistics

pdf
A Freely Available Wide Coverage Morphological Analyzer for English
Daniel Karp | Yves Schabes | Martin Zaidel | Dania Egedi
COLING 1992 Volume 3: The 14th International Conference on Computational Linguistics

pdf
XTAG - A Graphical Workbench for Developing Tree-Adjoining Grammars
Patrick Paroubek | Yves Schabes | Aravind K. Joshi
Third Conference on Applied Natural Language Processing

1991

pdf
Fixed and Flexible Phrase Structure: Coordination in Tree Adjoining Grammars
Aravind K. Joshi | Yves Schabes
Speech and Natural Language: Proceedings of a Workshop Held at Pacific Grove, California, February 19-22, 1991

pdf
The Valid Prefix Property and Left to Right Parsing of Tree-Adjoining Grammar
Yves Schabes
Proceedings of the Second International Workshop on Parsing Technologies

The valid prefix property (VPP), the capability of a left to right parser to detect errors as soon as possible, often goes unnoticed in parsing CFGs. Earley’s parser for CFGs (Earley, 1968; Earley, 1970) maintains the valid prefix property and obtains an O(n3)-time worst case complexity, as good as parsers that do not maintain such as the CKY parser (Younger, 1967; Kasami, 1965). Contrary to CFGs, maintaining the valid prefix property for TAGs is costly. In 1988, Schabes and Joshi proposed an Earley-type parser for TAGs. It maintains the valid prefix property at the expense of its worst case complexity (O(n9)-time). To our knowledge, it is the only known polynomial time parser for TAGs that maintains the valid prefix property. In this paper, we explain why the valid prefix property is expensive to maintain for TAGs and we introduce a predictive left to right parser for TAGs that does not maintain the valid prefix property but that achieves an O(n6)-time worst case behavior, O(n4)-time for unambiguous grammars and linear time for a large class of grammars.

pdf
Polynomial Time and Space Shift-Reduce Parsing of Arbitrary Context-free Grammars.
Yves Schabes
29th Annual Meeting of the Association for Computational Linguistics

1990

pdf bib
Using Lexicalized Tags for Machine Translation
Anne Abeille | Yves Schabes | Aravind K. Joshi
COLING 1990 Volume 3: Papers presented to the 13th International Conference on Computational Linguistics

pdf
Synchronous Tree-Adjoining Grammars
Stuart M. Shieber | Yves Schabes
COLING 1990 Volume 3: Papers presented to the 13th International Conference on Computational Linguistics

pdf
Two Recent Developments in Tree Adjoining Grammars: Semantics and Efficient Processing
Yves Schabes | Aravind K. Joshi
Speech and Natural Language: Proceedings of a Workshop Held at Hidden Valley, Pennsylvania, June 24-27,1990

pdf
Deterministic Left to Right Parsing of Tree Adjoining Languages
Yves Schabes | K. Vijay-Shanker
28th Annual Meeting of the Association for Computational Linguistics

pdf bib
Generation and Synchronous Tree-Adjoining Grammars
Stuart M. Shieber | Yves Schabes
Proceedings of the Fifth International Workshop on Natural Language Generation

pdf
The valid prefix property and parsing Tree Adjoining Grammars
Yves Schabes
Proceedings of the First International Workshop on Tree Adjoining Grammar and Related Frameworks (TAG+1)

1989

pdf
Lexicalized TAGs, Parsing and Lexicons
Anne Abeille | Kathleen Bishop | Sharon Cote | Aravind K. Joshi | Yves Schabes
Speech and Natural Language: Proceedings of a Workshop Held at Philadelphia, Pennsylvania, February 21-23, 1989

pdf
An Evaluation of Lexicalization in Parsing
Aravind K. Joshi | Yves Schabes
Speech and Natural Language: Proceedings of a Workshop Held at Cape Cod, Massachusetts, October 15-18, 1989

pdf
The Relevance of Lexicalization to Parsing
Yves Schabes | Aravind K. Joshi
Proceedings of the First International Workshop on Parsing Technologies

In this paper, we investigate the processing of the so-called ‘lexicalized’ grammar. In ‘lexicalized’ grammars (Schabes, Abeille and Joshi, 1988), each elementary structure is systema tically associated with a lexical ‘head’. These structures specify extended domains of locality (as compared to CFGs) over which constraints can be stated. The ‘grammar’ consists of a lexicon where each lexical item is associated with a finite number of structures for which that item is the ‘head’ . There are no separate grammar rules. There are, of course, ‘rules’ which tell us how these structures are combined. A general two-pass parsing strategy for ‘lexicalized’ grammars follows naturally. In the first stage, the parser selects a set of elementary structures associated with the lexical items in the input sentence, and in the second stage the sentence is parsed with respect to this set. We evaluate this strategy with respect to two characteristics. First, the amount of filtering on the entire grammar is evaluated: once the first pass is performed, the parser uses only a subset of the grammar. Second, we evaluate the use of non-local information: the structures selected during the first pass encode the morphological value (and therefore the position in the string) of their ‘head’; this enables the parser to use non-local in form ation to guide its search. We take Lexicalized Tree Adjoining Grammars as an in stance of lexicalized grammar. We illustrate the organization of the grammar. Then we show how a general Earley-type TAG parser (Schabes and Joshi, 1988) can take advantage of lexicalization. Empirical data show that the filtering of the grammar and the non-local in formation provided by the two-pass strategy improve the performance of the parser. We explain how constraints over the elementary structures expressed by unification equations can be parsed by a simple extension of the Earley-type TAG parser. Lexicalization guarantees termination of the algorithm without special devices such as restrictors.

pdf bib
Parsing Idioms in Lexicalized TAGs
Anne Abeille | Yves Schabes
Fourth Conference of the European Chapter of the Association for Computational Linguistics

1988

pdf
Parsing Strategies with ‘Lexicalized’ Grammars: Application to Tree Adjoining Grammars
Yves Schabes | Anne Abeille | Aravind K. Joshi
Coling Budapest 1988 Volume 2: International Conference on Computational Linguistics

pdf
An Earley-Type Parsing Algorithm for Tree Adjoining Grammars
Yves Schabes | Aravind K. Joshi
26th Annual Meeting of the Association for Computational Linguistics