Jane Robinson, a pioneering computational linguist, made major contributions to machine translation, natural language, and speech systems research programs at the RAND Corporation, IBM, and in the AI Center at SRI International. She served as ACL president in 1982.Jane became a computational linguist accidentally. She had a Ph.D. in history from UCLA, but could not obtain a faculty position in that field because those were reserved for men. Instead, she took positions teaching English, first at UCLA and then at California State College, Los Angeles. While at LA State, where she was tasked with teaching engineers how to write, Jane noticed an announcement for a talk on Chomsky's transformational grammar. She went to the talk thinking this work on grammar might help her teach better. Although its subject matter did not match her expectations, the talk marked a turning point in her career.In the late 1950s, Jane became a consultant to the RAND Corporation group working on machine translation under Dave Hays (ACL president, 1964). From the beginning, Jane was concerned with identifying connections between different traditions in formal grammars and their corresponding detailed linguistic realizations. Her 1965 International Conference on Computational Linguistics (COLING) paper, “Endocentric constructions and the Cocke parsing logic” (Robinson 1965), is a beautiful example of connecting specific linguistic phenomena to parsing strategies in a way that preserves the nature of the linguistic phenomena, endocentric constructions. While at RAND, Jane became colleague and friend to many in the machine translation and emerging computational linguistics world, including Susumo Kuno (ACL president 1967), Martin Kay (ACL president, 1969), Joyce Friedman (ACL president, 1971), and Karen Sparck Jones (ACL president, 1994).In the late 1960s, Jane moved to the Automata Theory and Computability Group at the IBM Thomas J. Watson Research Center in Yorktown Heights, NY. She used her knowledge of formal work on grammars and parsing to draw correspondences between Dependency Grammars and Phrase Structure Grammars. Although Jane came from the Dependency Grammar tradition, her balanced, careful analysis of tradeoffs enabled others to bridge the approaches. Her 1967 COLING paper, “Methods for obtaining corresponding phrase structure and dependency grammars” (Robinson 1967), is a wonderful example of her understanding of the seminal issues underlying these different systems. She subsequently published the classic paper connecting dependency structure and transformational rules, “Dependency structures and transformational rules” (Robinson 1970b). This paper exemplifies Jane's scholarship and her deftness in dealing with the formal and computational issues of language processing in a very fair and informative manner. Her 1970 paper, “Case, category and configuration” (Robinson 1970a), demonstrated in a very convincing way the possibility of formally interpreting Fillmore's case grammar in terms of dependencies, in a more economic fashion and without any loss of information.In 1973, Don Walker (ACL secretary-treasurer, 1976–1993) recruited Jane to the speech group in the AI Center (AIC) at SRI International. Jane remained a key member of the AIC's natural language group until she retired in the mid 1980s. She made major contributions to a wide range of research, ranging from grammars for speech understanding systems and dialogues to such discourse issues as codes and clues in contexts. For several of the NLP systems SRI developed in the 1970s and 1980s, the grammar was the coordinating point for all knowledge about the language, so Jane interacted with everyone developing any component of the system, from the architecture through semantics and discourse. Speech processing was a bit “deaf” in those days, and Jane frequently remarked that she had to write not only a grammar for English, but also its dual (one for non-English to rule out bad parsings). During her time at SRI, Jane wrote some of the most comprehensive grammars for NLP systems.One of us (Barbara Grosz) notes that Jane's contributions to the AIC's natural language group went far beyond her official grammar writing responsibilities. She served as mentor (before that word was widely used in academia) for a large group of “young Turks,” as she referred to those of us in the younger cohort involved in building NLP systems; she was our in-house expert in linguistics; provided critiques of drafts of papers, making them shorter, clearer, and more scholarly; debugged our ideas across the full spectrum of system components; and introduced us to the most senior people in linguistics and computational linguistics.Another of us (Aravind Joshi, ACL president, 1975) recalls meeting Jane in September 1975 at an NLP workshop at the University of Michigan. At that time, he and his students were working on two separate areas of computational linguistics. One of them concerned the minimal formal machinery needed for representing structural aspects of language and the other one dealt with some aspects of cooperation in natural language interfaces to databases. After just a brief discussion with Jane, when she asked what he was doing, it became clear to him, “that I was in the presence of someone who had already worked on such diverse areas. From thereon, whenever I had an opportunity to meet with Jane, I took advantage of her deep understanding.”And the third of us (Eva Hajicova, ACL president, 1998) recalls the important ties Jane formed with Praguian linguists interested in formal grammar starting in 1965, when the founder of the Prague group, Petr Sgall, first visited the United States and met Jane at RAND. Their common research interests in computational linguistics, particularly Dependency Grammar, forged deep personal relationships between Jane and Sgall's linguistics group in Prague. Jane visited Prague twice, once before and once after the change of the communist regime. During difficult political times, Jane provided the Prague group with linguistics literature published in the West, and she introduced them to her colleagues and students, yielding additional important connections, which have continued to this day. Eva notes that, “only those who have the same historical experience as we in Prague have had can appreciate fully how important such activities were for our research and for our students.”Jane read broadly and her training as a historian made her a careful and deep scholar. Throughout her life she would go to talks that seemed a bit far afield and come back with new ideas. For those who worked with her she was an invaluable source of out-of-the-box thinking as well as the go-to person for what to read in linguistics. Jane often said that had she been born in a later generation, she would have become an astronomer. Given her love of exploration, she might have been an astronaut. (You can see this bent in the poem she wrote for her poetry class friend's funeral, “Time To Go” [Robinson 2008]). Lucky for all of us, she wound up in computational linguistics.Jane was the mother of four children and the proud grandmother of two grandsons, one now a lawyer, the other an actor. She extended her family to encompass her colleagues, building camaraderie through dinners at her home—lamb stew, mostly— and picnics at Foothills Park in Palo Alto, activities which drew the families of AIC researchers together and yielded many lifelong friendships. Jane built such friendships throughout her career. In responding to our questions about Jane's time at RAND, Dave Hays's wife Rita noted that Jane remained close friends with her and Dave even after Dave went to SUNY Buffalo and Jane to IBM Yorktown Heights and then SRI. Rita and Jane were traveling and hiking companions into Jane's nineties.To celebrate her sixtieth birthday, Jane “got in shape” to hike in the Himalayas around Annapurna. She came back with beautiful photos and the desire to join the young Turks who went backpacking in Yosemite. (Although she had been a regular visitor to Yosemite since her forties, she had not backpacked before.) She offered to drive everyone in the huge Chrysler Imperial she had gotten to feel safe driving in New York. Jane backpacked into her late seventies, then switched to the luxury of the High Sierra Camp tent cabins and later to a small cabin with an inside shower. For those lucky enough to visit Yosemite with her, she was as much a guide to the mountains as she had been a guide to linguistics.For people who worked with Jane at SRI, she was a towering figure in the field, a wonderful colleague who imparted deep wisdom as well as linguistic facts, and a dear friend. She was senior to most of the members of the AIC. Looking back on her arrival, Peter Hart (a director of the AIC) noted that Jane's presence changed the tone of the early SRI AI Center. She brought not only a keen intellect and depth of knowledge, but “also a gentleness, openness, and generosity of spirit.” Gary Hendrix (who led the NLP group at SRI for several years) remembers that for many who worked with her at SRI, “Jane was like a second mother, loving and giving and nurturing.” Jerry Hobbs (ACL president, 1990) recalls that, “one of the things I learned from her, though imperfectly, was how to be tough with grace.” Several remember Jane as one of a handful of elder statesmen that their generation could look up to.Jane was a colleague and friend of Ray Perrault (ACL president, 1983, and current AIC director) from the time he was a Ph.D. student at the University of Michigan. In the early 1970s, Jane frequently visited Joyce Friedman (ACL president, 1971), her old friend and his advisor. Ray remembers Jane was a gentle but firm critic of his thesis, and he fondly recalls her passing through in her huge Chrysler on her move from IBM to SRI. Ray was ACL vice president when Jane was president, and she was delighted when he decided to join the young Turks at SRI. Subsequently, she “even tolerated me as her manager until her retirement and became doting godmother to my son.”Jane made a difference in people's lives, not just their research. Her death marks the end of an era and the passing of an icon. We will miss her greatly.This remembrance was a composite of the reminiscences of a number of people, including Tom Garvey, Marguerite Hays, Peter Hart, Gary Hendrix, Jerry Hobbs, David Israel, Ray Perrault, Candy Sidner, and Marty Tenenbaum.

The Penn Discourse Treebank (PDTB) was released to the public in 2008. It remains the largest manually annotated corpus of discourse relations to date. Its focus on discourse relations that are either lexically-grounded in explicit discourse connectives or associated with sentential adjacency has not only facilitated its use in language technology and psycholinguistics but also has spawned the annotation of comparable corpora in other languages and genres. Given this situation, this paper has four aims: (1) to provide a comprehensive introduction to the PDTB for those who are unfamiliar with it; (2) to correct some wrong (or perhaps inadvertent) assumptions about the PDTB and its annotation that may have weakened previous results or the performance of decision procedures induced from the data; (3) to explain variations seen in the annotation of comparable resources in other languages and genres, which should allow developers of future comparable resources to recognize whether the variations are relevant to them; and (4) to enumerate and explain relationships between PDTB annotation and complementary annotation of other linguistic phenomena. The paper draws on work done by ourselves and others since the corpus was released.

Recently, Kuhlmann (2007, Dependency Structures and Lexicalized Grammars. PhD Thesis, Saarland University) and collaborators have shown how the derivations of generative grammars can be recast as dependency structures. This connection between the generative and dependency traditions opens the door to a fresh perspective on how to formally characterize natural language and what minimal machinery can cover such data. This article draws on both reported properties of structures in dependency treebanks and properties of informant data to determine the complexity of natural language along two dependency measures, gap degree (a measure of discontinuity) and well- versus ill-nestedness (whether interleaving substructures are permitted). We show that natural language includes constructions that require dependency analyses that are ill-nested and/or gap degree > 1, and argue that a grammar formalism on the right track for characterizing natural language should be able to generate such structures. We investigate the adequacy of tree-local multi-component tree adjoining grammar (TL-MCTAG) to cover existent data, examining the relationship between TL-MCTAG derivations and dependency representations. Though focused on TL-MCTAG, this work also advances the larger enterprise of discovering mathematically defined formal systems and testing their adequacies by using both linguistic judgments as well as large bodies of data from annotated corpora.

BACKGROUND: Identification of discourse relations, such as causal and contrastive relations, between situations mentioned in text is an important task for biomedical text-mining. A biomedical text corpus annotated with discourse relations would be very useful for developing and evaluating methods for biomedical discourse processing. However, little effort has been made to develop such an annotated resource. RESULTS: We have developed the Biomedical Discourse Relation Bank (BioDRB), in which we have annotated explicit and implicit discourse relations in 24 open-access full-text biomedical articles from the GENIA corpus. Guidelines for the annotation were adapted from the Penn Discourse TreeBank (PDTB), which has discourse relations annotated over open-domain news articles. We introduced new conventions and modifications to the sense classification. We report reliable inter-annotator agreement of over 80% for all sub-tasks. Experiments for identifying the sense of explicit discourse connectives show the connective itself as a highly reliable indicator for coarse sense classification (accuracy 90.9% and F1 score 0.89). These results are comparable to results obtained with the same classifier on the PDTB data. With more refined sense classification, there is degradation in performance (accuracy 69.2% and F1 score 0.28), mainly due to sparsity in the data. The size of the corpus was found to be sufficient for identifying the sense of explicit connectives, with classifier performance stabilizing at about 1900 training instances. Finally, the classifier performs poorly when trained on PDTB and tested on BioDRB (accuracy 54.5% and F1 score 0.57). CONCLUSION: Our work shows that discourse relations can be reliably annotated in biomedical text. Coarse sense disambiguation of explicit connectives can be done with high reliability by using just the connective as a feature, but more refined sense classification requires either richer features or more annotated data. The poor performance of a classifier trained in the open domain and tested in the biomedical domain suggests significant differences in the semantic usage of connectives across these domains, and provides robust evidence for a biomedical sublanguage for discourse and the need to develop a specialized biomedical discourse annotated corpus. The results of our cross-domain experiments are consistent with related work on identifying connectives in BioDRB.

Supertagging is the tagging process of assigning the correct elementary tree of LTAG, or the correct supertag, to each word of an input sentence. In this paper we propose to use supertags to expose syntactic dependencies which are unavailable with POS tags. We first propose a novel method of applying Sparse Network of Winnow (SNoW) to sequential models. Then we use it to construct a supertagger that uses long distance syntactical dependencies, and the supertagger achieves an accuracy of 92.41%. We apply the supertagger to NP chunking. The use of supertags in NP chunking gives rise to almost 1% absolute increase (from 92.03% to 92.95%) in F-score under Transformation Based Learning(TBL) frame. The surpertagger described here provides an effective and efficient way to exploit syntactic information.

We argue in this article that many common adverbial phrases generally taken to signal a discourse relation between syntactically connected units within discourse structure instead work anaphorically to contribute relational meaning, with only indirect dependence on discourse structure. This allows a simpler discourse structure to provide scaffolding for compositional semantics and reveals multiple ways in which the relational meaning conveyed by adverbial connectives can interact with that associated with discourse structure. We conclude by sketching out a lexicalized grammar for discourse that facilitates discourse interpretation as a product of compositional rules, anaphor resolution, and inference.

Grammars are core elements of many NLP applications. In this paper, we present a system that automatically extracts lexicalized grammars from annotated corpora. The data produced by this system have been used in several tasks, such as training NLP tools (such as Supertaggers) and estimating the coverage of hand-crafted grammars. We report experimental results on two of those tasks and compare our approaches with related work.

We show that discourse structure need not bear the full burden of conveying discourse relations by showing that many of them can be explained nonstructurally in terms of the grounding of anaphoric presuppositions (Van der Sandt, 1992). This simplifies discourse structure, while still allowing the realisation of a full range of discourse relations. This is achieved using the same semantic machinery used in deriving clause-level semantics.

The use of constrained formal/computational systems just adequate for modeling various aspects of language—syntax, semantics, pragmatics and discourse, among others, has proved to be an effective research strategy leading to deep understanding of these aspects, with implications to both machine processing and human processing. This approach enables one to distinguish between the universal and stipulative constraints. This is in contrast to an approach where we start with the most powerful formal/computational system and then model the phenomena by making all constraints stipulative in a sense. The use of constrained systems for modeling leads to some novel ways of describing locality of structures and brings out the relationship between the complexity of description of primitives and local computations over them. These ideas serve to unify theoretical, computational and statistical aspects of natural languages processing in AI. It is expected that this approach will be productive in other domains of AI.

This paper describes the key aspects of a parser developed at the University of Pennsylvania from 1958 to 1959. The parser is essentially a cascade of finite state transducers. To the best of our knowledge, this is the first application of finite state transducers to parsing. This parser was recently faithfully reconstructed from the original documentation. Many aspects of this program have a close relationship to some of the recent work on finite state transducers.

In this paper we present some novel applications of Explanation-Based Learning (EBL) technique to parsing Lexicalized Tree-Adjoining grammars. The novel aspects are (a) immediate generalization of parses in the training set, (b) generalization over recursive structures and (c) representation of generalized parses as Finite State Transducers. A highly impoverished parser called a "stapler" has also been introduced. We present experimental results using EBL for different corpora and architectures to show the effectiveness of our approach.

No abstract available.

The findings of a workshop, the goals of which were to identify applications, research problems, and designs of high performance computing and communications (HPCC) systems for supporting applications are discussed. In computer vision, the main scientific issues are machine learning, surface reconstruction, inverse optics and integration, model acquisition, and perception and action. In speech and natural language processing (SNLP), issues were identified statistical analysis in corpus-based speech and language understanding, search strategies for language analysis, auditory and vocal-tract modeling, integration of multiple levels of speech and language analyses, and connectionist systems. In AI, important issues that need immediate attention include the development of efficient machine learning and heuristic search methods that can adapt to different architectural configurations, and the design and construction of scalable and verifiable knowledge bases, active memories, and artificial neural networks.>

In this paper the functional uncertainty machinery in LFG is compared with the treatment of long distance dependencies in TAG. It is shown that the functional uncertainty machinery is redundant in TAG, i.e., what functional uncertainty accomplishes for LFG follows from the TAG formalism itself and some aspects of the linguistic theory instantiated in TAG. It is also shown that the analyses provided by the functional uncertainty machinery can be obtained without requiring power beyond mildly context-sensitive grammars. Some linguistic and computational aspects of these results have been briefly discussed also.

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.

Recent results have established that there is a family of languages that is exactly the class of languages generated by three independently developed grammar formalisms: Tree Adjoining Grammars, Head Grammars, and Linear Indexed Grammars. In this paper we show that Combinatory Categorial Grammars also generates the same class of languages. We discuss the structural descriptions produced by Combinatory Categorial Grammars and compare them to those of grammar formalisms in the class of Linear Context-Free Rewriting Systems. We also discuss certain extensions of Combinatory Categorial Grammars and their effect on the weak generative capacity.

We consider the structural descriptions produced by various grammatical formalisms in terms of the complexity of the paths and the relationship between paths in the sets of structural descriptions that each system can generate. In considering the relationship between formalisms, we show that it is useful to abstract away from the details of the formalism, and examine the nature of their derivation process as reflected by properties of their derivation trees. We find that several of the formalisms considered can be seen as being closely related since they have derivation tree sets with the same structure as those produced by Context-Free Grammars. On the basis of this observation, we describe a class of formalisms which we call Linear Context-Free Rewriting Systems, and show they are recognizable in polynomial time and generate only semilinear languages.

We examine the relationship between the two grammatical formalisms: Tree Adjoining Grammars and Head Grammars. We briefly investigate the weak equivalence of the two formalisms. We then turn to a discussion comparing the linguistic expressiveness of the two formalisms.

The aim of this paper is to justify why Natural Language (NL) interaction, of a very rich functionality, is critical to the effective use of Expert Systems and to describe what is needed and what has been done to support such interaction. Interactive functions discussed here include defining terms, paraphrasing, correcting misconceptions, avoiding misconceptions, and modifying questions.

Tree Adjoining Grammar (TAG) is a formalism for natural language grammars. Some of the basic notions of TAG's were introduced in [Joshi, Levy, and Takahashi 1975] and by [Joshi, 1983]. A detailed investigation of the linguistic relevance of TAG's has been carried out in [Kroch and Joshi, 1985]. In this paper, we will describe some new results for TAG's, especially in the following areas: (1) parsing complexity of TAG's, (2) some closure results for TAG's, and (3) the relationship to Head grammars.

this paper, we investigate this revi.-ed principle as applied to question answering. In particular the goals of the research described here are to: 1. characterize tractable cases in which the system as respondent (R) can anticipate the possibility of the user/questioner (Q} drawing false conclusions from its response and can hence alter or expand its response so as to prevent it happening; 2. develop a formal method for computing the projected inferences that Q may draw from a particular response, identifylug those 1This work is partially supported by NSF Grants MCS 81-07290, MCS 8.3-05221, and [ST 88-1 2At present visiting the Department of Computer and Information Science, University of Pemsylvania, Phi|adelphia, PA 19104. factors whose presence or absence catalyzes the inferences; 3. enable the system to generate modifications of its response that can defuse possible false inferences and that may provide addi6oual useful information as well

Linguistic theories typically assign various linguistic phenomena to one of the categories, syntactic, semantic, or pragmatic, as if the phenomena in each category were relatively independent of those in the others. However, various phenomena in discourse do not seem to yield comfortably to any account that is strictly a syntactic or semantic or pragmatic one. This paper focuses on particular phenomena of this sort-the use of various referring expressions such as definite noun phrases and pronouns-and examines their interaction with mechanisms used to maintain discourse coherence.

D u r i n g t h e l a s t few y e a r s t h e r e i s v i g o r o u s activity In constructing highly constrained grammatical systems by eliminating the transformational component either totally or partially. There is increasing recognition of t he f a c t t h a t the e n t i r e r a n g e o f d e p e n d e n c i e s t h a t t r a n s f o r m a t i o n a l g r a m m a r s i n t h e i r v a r i o u s i n c a r n a t i o n s have t r i e d t o a c c o u n t f o r c a n be satisfactorily captured by classes of rules that are non-transformational and at the same Clme highly constrlaned in terms of the classes of g r a m m a r s and l a n g u a g e s t h a t t h e y de f i n e .

As I was reflecting deeply in front of the statue of Bodhisattva of Gr~ and Wisdom in the University Muset~n, I was startled to see Jane.Having heard from Don that he had asked the old cats to reflect on the 20 years of ACL, Jane had decided that she should drop in on some of them to seek their advice concerning the future of ACL.

My comments are organized within the framework suggested by the Panel Chair, Barbara Grosz, which I find very appropriate. All of my comments pertain to the various issues raised by her; however, wherever possible I will discuss these issues more in the context of the "information seeking" interaction and the data base domain.The primary question is how the purpose of the interaction or "the problem context" affects what is said and how it is interpreted. The two separate aspects of this question that must be considered are the function and the domain of the discourse.

No abstract available.

No abstract available.

The method of local constraints attempts to describe context-free languages in an apparently context-sensitive form which helps to retain the intuitive insights about the grammatical structure. This form of description, while apparently context-sensitive is, in fact, context-free and allows a program derivation structure to be represented as a tree with additional constraints, thus allowing for the possibility of a correctness proof in the form of Knuthian semantics. A part of ALGOL 60 syntax has been restated as a grammar with local constraints. It is also shown that parsing of grammars with local constraints can be carried out by a suitable extension of Early's algorithm. Finally, the relationship of local constraints to the semantics of programs is discussed in Section 4 by considering some program transformations.

It is very often more convenient and more meaningful to specify a set of structural descriptions analytically rather than generatively, i.e., by specifying a set of constraints each structured description in the set has to satisfy. Peters and Ritchie [7] have shown that if context-sensitive rules are used only for “analysis” then the string language of the set of trees is still context-free. In this paper, we have generalized this result by considering context-free rules constrained by Boolean combinations of proper analysis predicates and domination predicates. These rules, called "local transformations" not only make precise an informal and briefly discussed notion of Chomsky [2], but also, generalize it in an appropriate manner. It is shown that the Peters-Ritchie result can be generalized to local transformations. Linguistic relevance of this result has been also briefly discussed. Results in this paper are relevant to the following situation: Patterns of a class, say A, may be difficult to characterize generatively; but, it may be possible to specify a suitable (nontrivial) augmentation, say B, of the class A, such that B can be easily characterized generatively, and then A is characterized by stating some restrictions on the class B. This suggests possible applications to programming languages and pattern description languages.

Predicate complement constructions are a rich source of semantic problems. A system for testing the semantic properties (presuppositions and entailments) of predicate complement constructions has been constructed, and, in particular, the implementations of these constructions have been explored in some detail in the context of the tic-tac-toe game-playing setting of Isard and Longuet-Higgins [2] and Davies and Isard [1]. Even in such a limited setting, the implementations of many of these constructions (especially composite predicate complement constructions) are nontrivial, suggesting that such restricted settings provide a good testing ground for many key linguistic problems.

In this paper, we will essentially present three results in tree automata. Two of these are concerned with certain open problems posed by Rounds [1] and Martin and Vere [3], and the third one is related to the result of Peters and Ritchie [4].

Communication systems are considered in which there exists an auxiliary channel over which the receiver can make requests for retransmission. In general, it is assumed that the auxiliary channel is noiseless and the main channel is discrete and memoryless. It is also assumed that the a priori probabilities of the message symbols are known. A sequential receiver strategy is introduced which at each step minimizes the probability of retransmission subject to the condition that the probability of incorrect decoding does not exceed a given limit. The strategy is easy to implement in the case where group codes are used as error correctors and detectors. Moreover, in this case, conditions are given for which the strategy terminates with probability I, regardless of whether it is truncated. Examples are given for illustration.