Optimal k-arization of Synchronous Tree-Adjoining Grammar (2009)
Rebecca Nesson, Giorgio Satta, Stuart M. Shieber
Synchronous Tree-Adjoining Grammar (STAG) is a promising formalism for syntaxaware machine translation and simultaneous computation of natural-language syntax and semantics. Current research in both...
Towards Collaborative Intelligent Tutors: Automated Recognition of Users ’ Strategies (2009)
Elif Yamangil, Stuart M. Shieber, Andee Rubin, Barbara J. Grosz
Abstract. This paper addresses the problem of inferring students ’ strategies when they interact with data-modeling software that is used for pedagogical purposes. This software enables students to...
Synchronous grammars as tree transducers (2009)
Tree transducer formalisms were developed in the formal language theory community as generalizations of finite-state transducers from strings to trees. Independently, synchronous tree-substitution...
Prolog and Natural-Language Analysis Digital Edition Prolog and Natural-Language Analysis (2008)
Stuart M. Shieber, S. M. Shieber, S. M. Shieber
This work is the digital edition of Pereira and Shieber’s Prolog and Natural-Language Analysis. The work is also available for sale in a hardbound edition (ISBN 0-9719997-0-4), printed on acid-free...
Human-centered compression for efficient text input ∗ (2008)
Rani Nelken, Stuart M. Shieber
We describe a novel method for improving the efficiency of natural language text input under degraded conditions, for instance by disabled users or on mobile telephones. Previous approaches to this...
Writer's Aid: Using a Planner in a Collaborative Interface (2008)
Tamara Babaian, Barbara J. Grosz, Stuart M. Shieber
Writer's Aid is a collaborative system that works simultaneously with an author editing a document providing assistance in identifying and inserting citation keys and autonomously finding and...
Prolog and Natural-Language Analysis Digital Edition Prolog and Natural-Language Analysis (2008)
Stuart M. Shieber, S. M. Shieber, S. M. Shieber
This work is the digital edition of Pereira and Shieber’s Prolog and Natural-Language Analysis (revision of October 5, 2005). The work is also available for sale in a hardbound edition (ISBN...
Predicting Book Use for Off-Site Storage (2007)
Craig Silverstein, Stuart M. Shieber
We explore various methods for predicting library book use. Accurate prediction is invaluable when choosing titles to be stored in an off-site location. Previous researchers in this area concluded...
Stuart M. Shieber, Human Factors, Ellie Baker
We address the problem of improving the efficiency of natural language text input under degraded conditions (for instance, on PDAs or cell phones or by disabled users) by taking advantage of the...
Stuart M. Shieber, Veronica Dahl
This excellent book addresses the difficult and interesting task of providing a single theoretical and computational framework for the various grammar formalisms that have been characterized as...
Abstract Synchronous Tree-Adjoining Grammars (2007)
The unique properties of lree-adjoining grammars (TAG) present a challenge for the application of 'FAGs beyond the limited confines of syntax, for instance, to the task of semantic...
Stuart M. Shieber, Human Factors, Ellie Baker
We address the problem of improving the efficiency of natural language text input under degraded conditions (for instance, on PDAs or cell phones or by disabled users) by taking advantage of the...
Joe Marks, Joe Marks, Wheeler Ruml, Wheeler Ruml, Stuart M. Shieber, Stuart M. Shieber, ...
We present a new heuristic algorithm for graph bisection, based on an implicit notion of clustering. We describe how the heuristic can be combined with stochastic search procedures and a postprocess...
Extraction phenomena in synchronous TAG syntax and semantics (2007)
Rebecca Nesson, Stuart M. Shieber
We present a proposal for the structure of noun phrases in Synchronous Tree-Adjoining Grammar (STAG) syntax and semantics that permits an elegant and uniform analysis of a variety of phenomena,...
We provide a conceptual basis for thinking of machine translation in terms of synchronous grammars in general, and probabilistic synchronous tree-adjoining grammars in particular. Evidence for the...
Practical secrecy-preserving, verifiably correct and trustworthy auctions (2006)
David C. Parkes, Michael O. Rabin, Stuart M. Shieber, Christopher Thorpe
We present a practical protocol based on homomorphic cryptography for conducting provably fair sealed-bid auctions. The system preserves the secrecy of the bids, even after the announcement of...
Unifying Synchronous Tree-Adjoining Grammars and (2006)
Tree Transducers Via, Stuart M. Shieber
We place synchronous tree-adjoining grammars and tree transducers in the single overarching framework of bimorphisms, continuing the unification of synchronous grammars and tree transducers initiated...
Practical secrecy-preserving, verifiably correct and trustworthy auctions (2006)
David C. Parkes, Michael O. Rabin, Stuart M. Shieber, Christopher Thorpe
We present a practical protocol based on homomorphic cryptography for conducting provably fair sealed-bid auctions. The system preserves the secrecy of the bids, even after the announcement of...
Towards robust context-sensitive sentence alignment for monolingual corpora (2006)
Rani Nelken, Stuart M. Shieber
Aligning sentences belonging to comparable monolingual corpora has been suggested as a first step towards training text rewriting algorithms, for tasks such as summarization or paraphrasing. We...
Unifying synchronous treeadjoining grammars and tree transducers via bimorphisms (2006)
We place synchronous tree-adjoining grammars and tree transducers in the single overarching framework of bimorphisms, continuing the unification of synchronous grammars and tree transducers initiated...
THE TURING TEST AS INTERACTIVE PROOF (2006)
In this paper, I attempt to reconcile two mutually contradictory but well-founded attitudes towards the Turing Test, Alan Turing’s proposed replacement for the question “Can machines think? ”...
Practical secrecy-preserving, verifiably correct and trustworthy auctions (2006)
David C. Parkes, Michael O. Rabin, Stuart M. Shieber, D. C. Parkes, M. O. Rabin, S. M. Shieber, ...
We present a practical system for conducting sealed-bid auctions that preserves the secrecy of the bids while providing for verifiable correctness and trustworthiness of the auction. The auctioneer...
Towards robust context-sensitive sentence alignment for monolingual corpora (2006)
Rani Nelken, Stuart M. Shieber
nelken,shieber¡ Aligning sentences belonging to comparable monolingual corpora has been suggested as a first step towards training text rewriting algorithms, for tasks such as summarization or...
Human-centered compression for efficient text input (2006)
Nelken, Rani, Shieber, Stuart M.
Traditional methods for efficient text entry are based on prediction. Prediction requires a constant context-shift between entering text and selecting or verifying the predictions. Previous research...
Practical secrecy-preserving, verifiably correct and trustworthy auctions (2006)
David C. Parkes, David C. Parkes, Michael O. Rabin, Stuart M. Shieber, Christopher Thorpe, Michael O. Rabin, ...
Practical secrecy-preserving, verifiably correct and trustworthy auctions.
A learning approach to improving sentence-level MT evaluation (2004)
Alex Kulesza, Stuart M. Shieber
The problem of evaluating machine translation (MT) systems is more challenging than it may first appear, as diverse translations can often be considered equally correct. The task is even more...
A learning approach to improving sentence-level MT evaluation (2004)
Alex Kulesza, Stuart M. Shieber
The problem of evaluating machine translation (MT) systems is more challenging than it may first appear, as diverse translations can often be considered equally correct. The task is even more...
Comma restoration using constituency information (2003)
Stuart M. Shieber, Xiaopeng Tao
Automatic restoration of punctuation from unpunctuated text has application in improving the fluency and applicability of speech recognition systems. We explore the possibility that syntactic...
Parse disambiguation for a rich hpsg grammar (2002)
Kristina Toutanova, Christopher D. Manning, Stuart M. Shieber, Þ Dan Flickinger, Stephan Oepen Ý
In this paper, we describe experiments on HPSG parse disambiguation using the Redwoods HPSG treebank (Oepen et al. 2002a,b,c). HPSG is a constraint-based lexicalist (“unification”) grammar...
Parse disambiguation for a rich hpsg grammar (2002)
Kristina Toutanova, Christopher D. Manning, Stuart M. Shieber, Dan Flickinger, Stephan Oepen
In this paper, we describe experiments on HPSG parse disambiguation using the Redwoods HPSG treebank (Oepen et al. 2002a,b,c). HPSG is a constraint-based lexicalist (“unification”) grammar...
A Writer's Collaborative Assistant (2002)
Tamara Babaian, Barbara J. Grosz, Stuart M. Shieber
In traditional human-computer interfaces, a human master directs a computer system as a servant, telling it not only what to do, but also how to do it. Collaborative interfaces attempt to realign the...
Parse Disambiguation for a Rich HPSG Grammar (2002)
Kristina Toutanova Christopher, Christopher D. Manning, Stuart M. Shieber, Dan Flickinger, Stephan Oepen
this paper, we describe experiments on HPSG parse disambiguation using the Redwoods HPSG treebank (Oepen et al. 2002a,b,c). HPSG is a constraint-based lexicalist ("unification") grammar...
Seed-Growth Heuristics for Graph Bisection (1999)
Wheeler Ruml, Joe Marks, Stuart M. Shieber, J. Thomas Ngo
We investigate a family of algorithms for graph bisection that are based on a simple local connectivity heuristic, which we call seedgrowth. We show how the heuristic can be combined with stochastic...
A Seed-Growth Heuristic for Graph Bisection (1998)
Joe Marks, Wheeler Ruml, Stuart M. Shieber, J. Thomas Ngo
We present a new heuristic algorithm for graph bisection, based on an implicit notion of clustering. We describe how the heuristic can be combined with stochastic search procedures and a postprocess...
A Seed-Growth Heuristic for Graph Bisection (1998)
Joe Marks, Wheeler Ruml, Stuart M. Shieber, J. Thomas Ngo
We present a new heuristic algorithm for graph bisection, based on an implicit notion of clustering. We describe how the heuristic can be combined with stochastic search procedures and a postprocess...
Tree-adjoining grammars (1997)
Tree-adjoining grammars (TAG) have been proposed as a formalism for generation based on the intuition that the extended domain of syntactic locality that TAGs provide should aid in localizing...
Human-Computer Communication And Collaboration (1997)
Barbara J. Grosz, Stuart M. Shieber
entral to the success of dialogues in human collaborations; for instance, they do not use information about what a person is trying to achieve nor adequately model the dialogue context. As a result,...
A General Cartographic Labeling Algorithm (1997)
Shawn Edmondson, Jon Christensen, Joe Marks, Stuart M. Shieber, Contact Stuart, M. Shieber
Some apparently powerful algorithms for automatic label placement on maps use heuristics that capture considerable cartographic expertise but are hampered by provably inefficient methods of search...
Interactions of Scope and Ellipsis (1996)
Stuart M. Shieber, Mary Dalrymple
Systematic semantic ambiguities result from the interaction of the two operations that are involved in resolving ellipsis in the presence of scoping elements such as quantifiers and intensional...
A General Cartographic Labeling Algorithm (1996)
Shawn Edmondson, Jon Christensen, Joe Marks, Stuart M. Shieber
Some apparently powerful algorithms for automatic label placement on maps use heuristics that capture considerable cartographic expertise but are hampered by provably inefficient methods of search...
Predicting Individual Book Use for Off-Site Storage Using Decision Trees (1996)
Craig Silverstein, Stuart M. Shieber
We explore various methods for predicting library book use, as measured by circulation records. Accurate prediction is invaluable when choosing titles to be stored in an off-site location. Previous...
Ellipsis and Higher-Order Unification (1995)
Dalrymple, Mary, Shieber, Stuart M., Pereira, Fernando C. N.
We present a new method for characterizing the interpretive possibilities generated by elliptical constructions in natural language. Unlike previous analyses, which postulate ambiguity of...
Principles and Implementation of Deductive Parsing (1995)
Stuart Shieber Division, Stuart M. Shieber, Yves Schabes
We present a system for generating parsers based directly on the metaphor of parsing as deduction. Parsing algorithms can be represented directly as deduction systems, and a single deduction engine...
Principles And Implementation Of Deductive Parsing (1995)
Stuart M. Shieber, Yves Schabes
We present a system for generating parsers based directly on the metaphor of parsing as deduction. Parsing algorithms can be represented directly as deduction systems, and a single deduction engine...
Principles and Implementation of Deductive Parsing (1994)
Shieber, Stuart M., Schabes, Yves, Pereira, Fernando C. N.
We present a system for generating parsers based directly on the metaphor of parsing as deduction. Parsing algorithms can be represented directly as deduction systems, and a single deduction engine...
An Alternative Conception of Tree-Adjoining Derivation (1994)
Schabes, Yves, Shieber, Stuart M.
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...
Lessons from a Restricted Turing Test (1994)
We report on the recent Loebner prize competition inspired by Turing's test of intelligent behavior. The presentation covers the structure of the competition and the outcome of its first...
Restricting the Weak-Generative Capacity of Synchronous Tree-Adjoining Grammars (1994)
The formalism of synchronous tree-adjoining grammars, a variant of standard tree-adjoining grammars (TAG), was intended to allow the use of TAGs for language transduction in addition to language...
Principles and Implementation of Deductive Parsing (1994)
Stuart M. Shieber, Yves Schabes
We present a system for generating parsers based directly on the metaphor of parsing as deduction. Parsing algorithms can be represented directly as deduction systems, and a single deduction engine...
A Recursive Coalescing Method for Bisecting Graphs (1994)
Stuart M. Shieber, Bryan Mazlish, Bryan Mazlish, Stuart Shieber, Joe Marks, Joe Marks
We present an extension to a hybrid graph-bisection algorithm developed by Bui et al. that uses vertex coalescing and the Kernighan-Lin variabledepth algorithm to minimize the size of the cut set. In...
Principles and Implementation of Deductive Parsing (1994)
Stuart M. Shieber, Yves Schabes
We present a system for generating parsers based directly on the metaphor of parsing as deduction. Parsing algorithms can be represented directly as deduction systems, and a single deduction engine...
An Alternative Conception of (1994)
Yves Schabes, Stuart M. Shieber
this paper, we argue that previous definitions of tree-adjoining derivation have not taken full advantage of this decoupling, and are not as appropriate as they might be for the kind of further...
Restricting the weak-generative capacity of synchronous tree-adjoining grammars (1994)
Abstract. The formalism of synchronous tree-adjoining grammars, a variant of standard tree-adjoining grammars (TAG), was intended to allow the use of TAGs for language transduction in addition to...
An Alternative Conception of Tree-Adjoining Derivation (1994)
Yves Schabes, Stuart M. Shieber, Mitsubishi Electric
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...
Automating the Layout of Network Diagrams with Specified Visual Organization (1993)
Stuart M. Shieber, Corey Kosak, Corey Kosak, Joe Marks, Joe Marks, Stuart Shieber
Network diagrams are a familiar graphic form that can express many different kinds of information. The problem of automating network-diagram layout has therefore received much attention. Previous...
Lessons from a Restricted Turing Test (1993)
We report on the recent Loebner prize competition inspired by Turing's test of intelligent behavior. The presentation covers the structure of the competition and the outcome of its first...
The Turing Test and the Loebner Prize (1993)
We report on the recent Loebner prize competition inspired by Turing's test of intelligent behavior. The presentation covers the structure of the competition and the outcome of its first...
The Problem of Logical-Form Equivalence (1992)
this paper, I review the problem, and attempt to highlight certain salient aspects of it that have been lost in the pursuing of solutions, in order to reconcile the apparently contradictory claims of...
Generation and Synchronous Tree-Adjoining Grammars (1992)
Stuart M. Shieber, Yves Schabes
Tree-adjoining grammars (TAG) have been proposed as a formalism for generation based on the intuition that the extended domain of syntactic locality that TAGs provide should aid in localizing...
Generation and Synchronous Tree-Adjoining Grammars (1991)
Shieber, Stuart M, Schabes, Yves
The recent history of grammar reversing can be viewed as an effort to recover seine notion of semantic locality on which to base a generation process. For instance, Wedekind (1988) requires a...
Synchronous Tree-Adjoining Grammars (1991)
Shieber, Stuart M, Schabes, Yves
The unique properties of tree-adjoining grammars (TAG) present a challenge for the application of TAGs beyond the limited confines of syntax, for instance, to the task of semantic interpretation or...
Ellipsis and Higher-Order Unification (1991)
Mary Dalrymple, Stuart M. Shieber
We present a new method for characterizing the interpretive possibilities generated by elliptical constructions in natural language. Unlike previous analyses, which postulate ambiguity of...
Semantic-head-driven generation (1990)
Stuart M. Shieber, Gertjan Van Noord, Robert C. Moore
We present an algorithm for generating strings from logical form encodings that improves upon previous algorithms in that it places fewer restrictions on the class of grammars to which it is...
Parsing and type inference for natural and computer languages / (1989)
Abstract: "Computational and theoretical linguists and computer scientists interested in the computer processing of natural language have converged on a class of grammar formalisms for describing the...
Parsing and type inference for natural and computer languages /--by Stuart M. Shieber. (1989)
Thesis (Ph. D.)--Stanford University, 1989
A semantic-head-driven generation algorithm for unification-based formalisms (1989)
Stuart M. Shieber, Gertjan Van Noord
We present an algorithm for generating strings from logical form encodings that improves upon previous algorithms in that it places fewer restric-tions on the class of grammars to which it is...
An algorithm for generating quantifier scopings (1987)
Jerry R. Hobbs, Stuart M. Shieber
The syntactic structure of a sentence often manifests quite clearly the predicate-argument structure and relations of grammatical subordination. But scope dependencies are not so transparent. As a...
An Algorithm for Generating Quantifier Scopings (1987)
Jerry Hobbs, Stuart M. Shieber
The syntactic structure of a sentence often manifests quite clearly the predicateargument structure and relations of grammatical subordination. But scope dependencies are not so transparent. As a...
Using restriction to extend parsing algorithms for complex-feature-based formalisms (1985)
Grammar formalisms based on the encoding of grammatical information in complex-valued feature systems enjoy some currency both in linguistics and natural-language-processing research. Such formalisms...
Formal Constraints on Metarules (1983)
Stuart M. Shieber, Susan U. Stucky, Hans Uszkoreit, Jane J. Robinson
Metagrammaticai formalisms that combine context-free phrase structure rules and metarules (MPS grammars) allow concise statement of generalizations about the syntax of natural languages....
Equity for Open-Access Journal Publishing
Open-access journals, which provide access to their scholarly articles freely and without limitations, are at a systematic disadvantage relative to traditional closed-access journal publishing and...
Equity for Open-Access Journal Publishing
Open access journal publishing is currently at a systematic disadvantage relative to the traditional subscription-based journal publishing. A simple, cost effective remedy to this inequity is...