Search

This document describes the software requirements of a Joint Tactical Radio System (JTRS) Software Communications Architecture (SCA) implementation called the Core Framework (CF). This Software Requirements Specification (SRS) defines the requirements for the Open Radio Communications Architecture Core Framework (OrcaCF) v1.1.0 in accordance with the JTRS SCA version 2.2. The CF software package contains: an Operating System per SCA v2.2, Section 3.1.1, Middleware and Services per SCA v2.2, Section 3.1.2, a Core Framework per SCA v2.2, Section 3.1.3, and a simple application per SCA v2.2, Section 3.2. The OrcaCF was developed on a standard Intel x86-based PC running the Linux Operating System (OS) from RED HAT., The original document contains color images.

This Quick Reference Guide (QRG) describes the installation and operation of the Open Radio Communications Architecture Core Framework (OrcaCF) v1.1.0 developed by L-3 Communications Government Services Inc. (L3) for Air Force Research Laboratory (AFRL). The OrcaCF implements the Joint Tactical Radio System (JTRS) Software Communications Architecture (SCA) version 2.2 specification. It was developed in C++ and uses ACE/TAO for CORBA middleware, Xerces for the SML parser, and Linux for the Operating System. The OrcaCF was derived from the LinuxCF v1.1.1 which was delivered to the JTeL in October 2003. However, it is significantly superior to the LinuxCF v1.1.1 with increased stability; better thread management; better exception handling; more complete XML parsing and better installation scripts. The OrcaCF v1.1.0 has also been thoroughly tested using the JTRS Test Application (JTAP)., The original document contains color images.

A framework for studying texture in general, and for texture mixing in particular, is presented in this paper. The work follows concepts from universal type classes and universal simulation. Based on the well-known Lempel and Ziv (LZ) universal compression scheme, the universal type class of a one dimensional sequence is defined as the set of possible sequences of the same length which produce the same dictionary (or parsing tree) with the classical LZ incremental parsing algorithm. Universal simulation is realized by sampling uniformly from the universal type class, which can be efficiently implemented. Starting with a source texture image, we use universal simulation to synthesize new textures that have, asymptotically, the same statistics of any order as the source texture, yet have as much uncertainty as possible, in the sense that they are sampled from the broadest pool of possible sequences that comply with the statistical constraint. When considering two or more textures, a parsing tree is constructed for each one, and samples from the trees are randomly interleaved according to pre-defined proportions, thus obtaining a mixed texture. As with single texture synthesis, the k-th order statistics of this mixture, for any k, asymptotically approach the weighted mixture of the k-th order statistics of each individual texture used in the mixing. We present the underlying principles of universal types, universal simulation, and their extensions and application to mixing two or more textures with pre-defined proportions., Institue for Mathematics and Its Applications (IMA) Preprint Series. Performed in cooperation with Universidad de la Republica-Uruguay; and Helwett-Packard Laboratories.

Extraction of intelligence from text data is increasingly becoming automated as software and network technology increases in speed and scope. However, enormous amounts of text data are often available and one must carefully design a data mining strategy to obtain the relevant nuggets of gold from the mountains of useless dross. Two strategies can be tried. A deep approach is to use a few strong clues to find reasonable sentence candidates, then apply linguistic restrictions to find and extract key information (if any) surrounding the candidates. A broad approach is to focus on large numbers of weaker clues such as specific words whose implications can be combined to rate sentences and present those of high likelihood of relevance. In the work reported here, we tested the deep approach on military intelligence reports about enemy positions, which were relatively short text extracts, and we tested the broad approach on news stories from the World Wide Web involving terrorism, which presented a large volume of text information., Presented at the International Command and Control Research and Technology Symposium (ICCRTS) (10th) held in McLean, VA on 13-16 Jun 2005. Published in the Proceedings of the International Command and Control Research and Technology Symposium (ICCRTS) (10th), 2005. Briefing charts included. Sponsored in part by DARPA. The original document contains color images.

With the move to High-Level Architecture and the Modeling Architecture for Technology Research EXperimentation (MATREX) suite, the U.S. Army Research Laboratory Vulnerability/Lethality Server required the ability to read the new database format for vulnerability probabilities. Support was provided through a component to read these database files, find the stored probabilities, and compute the probability packing suitable for selecting an end condition given a random number. The component implements a fast parameter-driven reentrant interface, as well as a compatibility interface based on the server's global values. The new ModSAF "reader" (RDR) file format parser and lookup component provides a high-performance and simple way to extract vulnerability probabilities from MATREX RDR files. While the software was written to support the server software package, the interface to the core RDR parser was made in a generic fashion. This report describes the design and implementation of the component, how to interface it, and a performance analysis as compared to the alternative individual unit of action table component.

Knowledge-Rich Acquisition of Knowledge from Experts Who Are Non-logicians (KRAKEN) was performed under DARPA's Rapid Knowledge Formation (RKF) Program. The KRAKEN system allows Subject Matter Experts (SMEs) to more easily, efficiently, and correctly enter their knowledge into an artificial intelligence knowledge-based system. KRAKEN's usefulness has been demonstrated in three challenge problems related to molecular biology, authoring of course-of-action (CA) critiquing rules, and terrain analysis. This report contains a description of KRAKEN, a Knowledge Entry system developed as part of the Rapid Knowledge Formation Project, funded by DARPA. In addition to describing the KRAKEN system as it exists today, this report also discusses the development of the system, its performance in three annual evaluations, the lessons learnt that are of general interest to the community of knowledge entry systems developers, and specific insights for future research. The following are goals for the KRAKEN System: Rich Tools - the knowledge entry tools must themselves be knowledge-based; Multidimensional Context Tools - the system must model the user's context to display appropriate information, offer suitable choices of action, and interpret the user's action; Deeply Understand Text; Clarification and Discourse; Planning and Problem Solving; Explicit Reasoning about KE Methodology itself; KBs to fix KBs; Pegs3 - the NL understanding must be able to cope with anaphora and cataphora; Mix and Match - must be able to work within a heterogeneous array of different systems; Metaphors and Analogies - must be able to interpret metaphors, analogies, and similes; Active Collaboration Aid and Control - must support a collaborative mode of working whereby SMEs can share work and correct or review each other's work; Automated Tracking of Metrics; and Ultimate Impact - the system must provide a significant potential benefit to DoD and industry and institutions. (5 tables, 37 figures), The original document contains color images.

A natural way to communicate with C2 systems would be to use natural language. Natural language components are already used in military systems, for example, CommandTalk is a spoken-language interface to the ModSAF battlefield simulator. In project SOKRATES, the authors use shallow parsing techniques for written language to analyze German free-form battlefield reports. These reports are processed by transducers. The extraction result is formalized in feature structures, semantically enriched by the semantic analysis, and the augmented result is then stored in the ATCCIS database. After storage in the database, triggers initiate a change in the position of a tactical symbol on the tactical map. Shallow parsing techniques are the basis for information extraction. In this paper, the authors first introduce the promising field of information extraction, and then describe in detail how shallow parsing techniques are used in project SOKRATES. Twenty-four briefing charts summarize the presentation. (2 figures, 15 refs.), See also ADM001673. Published in RTO-MP-IST-040. Presented at the Information Systems Technology Panel (IST) symposium on "Military Data and Information Fusion (La fusion des informations et de donnes militaires)" held in Prague, Czech Republic, on 20-22 Oct 2003. The original document contains color images.

This paper discusses a memory architecture that realizes a group structure of data filters on a lattice of control strings (sets). The lattice filters concatenate & parse control strings for memory I/0 using a method that in various ways mirrors' orthogonal quadrature signal filtering from wavelet theory (thus the name). The lattice indicates algebraic structures, of partial orders & set inclusion, that filters perform on the control string sets'. There are many ways to realize memorization of controls for system configuration: this is one way that I found interesting for its algebraic structure.

A key problem in indexing technical information is the interpretation of technical words and word senses, expressions not used in everyday language. This is important for captions on technical images, whose often pithy descriptions can be valuable to decipher. We describe the natural-language processing for MARIE-2, a natural-language information retrieval system for multimedia captions. Our approach is to provide general tools for lexicon enhancement with the specialized words and word senses, and to learn word usage information (both on word senses and word-sense pairs) from a training corpus with a statistical parser. Innovations of our approach are in statistical inheritance of binary co-occurrence probabilities and in weighting of sentence subsequences. MARIE-2 was trained and tested on 616 captions (with 1009 distinct sentences) from the photograph library of a Navy laboratory. The captions had extensive nominal compounds, code phrases, abbreviations, and acronyms, but few verbs, abstract nouns, conjunctions, and pronouns. Experimental results fit a processing time in seconds of 876.2 0858.0 n and a number of tries before finding the best interpretation of 668 .1809.1 n where n is the number of words in the sentence. Use of statistics from previous parses definitely helped in reparsing the same sentences, helped accuracy in parsing of new sentences, and did not hurt time to parse new sentences. Word-sense statistics helped dramatically; statistics on word-sense pairs generally helped but not always., The original document contains color images.

Many probabilistic models for natural language are now written in terms of hierarchical tree structure. Tree-based modeling still lacks many of the standard tools taken for granted in (finite-state) string-based modeling. The theory of tree transducer automata provides a possible framework to draw on, as it has been worked out in an extensive literature. We motivate the use of tree transducers for natural language and address the training problem for probabilistic tree-to-tree and tree-to-string transducers., Presented at The Human Language Technology and North American Chapter of the Association for Computational Linguistics Conference (HLT-NAACL), held in Boston, MA on 2-5 May, 2004. Pub. in the Proceedings of The Human Language Technology and North American Chapter of the Association for Computational Linguistics Conference (HLT-NAACL), 2004. Sponsored in part by Advanced Research and Development Activity (ARDA), Ft. Meade, MD.

A number of issues arise when trying to scale-up natural language understanding (NLU) tools designed for relatively simple domains (e.g. flight information) to domains such as medical advising or tutoring where deep understanding of user utterances is necessary. Because the subject matter is richer, the range of vocabulary and grammatical structures is larger meaning NLU tools are more likely to encounter out-of-vocabulary words or extra-grammatical utterances. This is especially true in medical advising and tutoring where users may not know the correct vocabulary and use common sense terms or descriptions instead. Techniques designed to improve robustness (e.g., skipping unknown words, relaxing grammatical constraints, mapping unknown words to known words) are effective at increasing the number of utterances for which an NLU sub-system can produce a semantic interpretation. However, such techniques introduce additional ambiguity and can lead to a loss of fidelity (i.e., a mismatch between the semantic interpretation and what the language producer meant). To control this trade-off, we propose semantic interpretation confidence scores akin to speech recognition confidence scores and describe our initial attempt to compute such a score in a modularized NLU sub-system., Presented at the International Workshop on Scalable Natural Language Understanding (2nd) (ScaNaLU) at HLT-NAACL held in Boston, MA on 6 May 2004. Published in the Proceedings of the International Workshop on Scalable Natural Language Understanding (2nd), 2004.

In this paper, we explore the use of automatic syntactic simplification for improving content selection in multi-document summarization. In particular, we show how simplifying parentheticals by removing relative clauses and appositives results in improved sentence clustering, by forcing clustering based on central rather than background information. We argue that the inclusion of parenthetical information in a summary is a reference-generation task rather than a content-selection one, and implement a baseline reference rewriting module. We perform our evaluations on the test sets from the 2003 and 2004 Document Understanding Conference and report that simplifying parentheticals results in significant cant improvement on the automated evaluation metric Rouge. Syntactic simplification is an NLP task, the goal of which is to rewrite sentences to reduce their grammatical complexity while preserving their meaning and information content. Text simplification is a useful task for varied reasons. Chandrasekar et al. (1996) viewed text simplification as a preprocessing tool to improve the performance of their parser. The PSET project (Carroll et al., 1999), on the other hand, focused its research on simplifying newspaper text for aphasics, who have trouble with long sentences and complicated grammatical constructs. We have previously (Siddharthan, 2002; Siddharthan, 2003) developed a shallow and robust syntactic simplification system for news reports, that simplifies relative clauses, apposition and conjunction. In this paper, we explore the use of syntactic simplification in multi-document summarization.

The lack of sentence boundaries and presence of disfluencies pose difficulties for parsing conversational speech. This work investigates the effects of automatically detecting these phenomena on a probabilistic parser's performance. We demonstrate that a state-of-the-art segmenter, relative to a pause-based segmenter, gives more than 45% of the possible error reduction in parser performance, and that presentation of interruption points to the parser improves performance over using sentence boundaries alone. Parsing speech can be useful for a number of tasks, including information extraction and question answering from audio transcripts. However, parsing conversational speech presents a different set of challenges than parsing text: sentence boundaries are not well-defined, punctuation is absent, and disfluencies (edits and restarts) impact the structure of language.

This grant supported the writing of a book on the author's experiments in human and computer tutoring and enabled the running of one last experiment with the CIRCSIM-Tutor system, Version 2.9. The experiment compared the learning gains made by medical students using the CIRCSIM-Tutor system with those made by students reading a carefully edited relevant text. The experiment was suggested at a meeting of ONR Grantees in the tutoring portion of the Cognitive Science Program. The author carried out this experiment in November 2002. It showed, as she had hoped, that the 40 students who used CIRCSIM-Tutor for an hour made significantly greater learning gains than the 33 who read a carefully chosen and edited text. What is more, over 80% of the CIRCSIM-Tutor students completed all eight problems as opposed to 60% in the experiment in November 1999. The system did not crash. It corrected 104 spelling errors without making any identifiable miscorrections, and it did not get caught up in any of the confusions that turned up in earlier experiments. The students expressed enthusiasm about the tutor. None of them felt compelled to curse the system, as had happened in the past. The author would like to believe that this was because it was less frustrating to use, but it may just have been due to the number of observers present. This report describes the results of the experiment, gives a more detailed description of the natural language understanding results, and summarizes some of the author's other current research. A bibliography of 14 publications is included., Originally funded under BAA-02-001 Long-Range Scientific and Technology Program.

Formal methods hold significant potential for automating the development, refinement, and implementation of policy. For this potential to be realized, however, improved techniques are required for converting natural-language statements of policy into a computational form. In this paper we present and analyze an architecture for carrying out this conversion. The architecture employs semantic networks to represent both policy statements and objects in the domain of those statements. We present a case study which illustrates how a system based on this architecture could be developed. The case study consists of an analysis of natural language policy statements taken from a policy document for web sites at a university, and is carried out with support from a software tool we developed which converts text output from a natural language parser into a graphical form., The original document contains color images.

Syntactic structure is an important component of natural language utterances, for both form and content. Therefore, a variety of applications can benefit from the integration of syntax into their statistical models of language. In this thesis, two new syntax-based models are presented, along with their training algorithms: a monolingual generative model of sentence structure, and a model of the relationship between the structure of a sentence in one language and the structure of its translation into another language. After these models are trained and tested on the respective tasks of monolingual parsing and word-level bilingual corpus alignment, they are demonstrated in two additional applications. First, a new statistical parser is automatically induced for a language in which none was available, using a bilingual corpus. Second, a statistical translation system is augmented with syntax-based models. Thus the contributions of this thesis include: a statistical parsing system; a bilingual parsing system, which infers a structural relationship between two languages using a bilingual corpus; a method for automatically building a parser for a language where no parser is available; and a translation model that incorporates phrase structure., Sponsored in part by National Science Foundation (NSF), grant no. IIS-0312814.

We introduce a probabilistic noisy-channel model for question answering and we show how it can be exploited in the context of an end-to-end QA system. Our noisy-channel system outperforms a state-of-the-art rule-based QA system that uses similar resources. We also show that the model we propose is flexible enough to accommodate within one mathematical framework many QA-specific resources and techniques, which range from the exploitation of WordNet, structured, and semi-structured databases to reasoning and paraphrasing., Presented at the Annual Meeting of the Association for Computational Linguistics (41st) held in Sapporo, Japan on 7-12 July 2003. Published in the Proceedings of the Annual Meeting of the Association for Computational Linguistics (41st), p16-23, 2003.

A logical framework is a general meta-language for specifying and implementing deductive systems, given by axioms and inference rules. Based on a higher-order logic programming interpretation, it supports executing logical systems and reasoning with and about them, thereby reducing the effort required for each particular logical system. In this thesis, we describe different techniques to improve the overall performance and the expressive power of higher-order logic programming. First, we introduce tabled higher-order logic programming, a novel execution model where some redundant information is eliminated using selective memoization. This extends tabled computation to the higher-order setting and forms the basis of the tabled higher-order logic programming interpreter. Second, we present efficient data-structures and algorithms for higher-order proof search. In particular, we describe a higher-order assignment algorithm which eliminates many unnecessary occurs checks and develop higher-order term indexing. These optimizations are crucial to make tabled higher-order logic programming successful in practice. Finally, we use tabled proof search in the meta-theorem prover to reason efficiently with and about deductive systems. It takes full advantage of higher-order assignment and higher-order term indexing. As experimental results demonstrate, these optimizations taken together constitute a significant step toward exploring the full potential of logical frameworks in practice., Sponsored in part by the National Science Foundation under Grant No., CCR-9988281.

This paper presents Hedge Trimmer a HEaDline GEneration system that creates a headline for a newspaper story using linguistically-motivated heuristics to guide the choice of a potential headline. We present feasibility tests used to establish the validity of an approach that constructs a headline by selecting words in order from a story. In addition we describe experimental results that demonstrate the effectiveness of our linguistically-motivated approach over a HMM-based model using both human evaluation and automatic metrics for comparing the two approaches., Sponsored in part by NSF Grant no. EIA0130422. Presented at the HLT-NAACL Workshop on Text Summarization held in Edmonton, Canada on 31 May-1 June 2003. Published in the Proceedings of the HLT-NAACL Workshop on Text Summarization, 2003.

We present a system for automatically identifying PropBank-style semantic roles based on the output of a statistical parser for Combinatory Categorical Grammar. This system performs at least as well as a system based on a traditional Treebank parser, and outperforms it on core argument roles.

This paper reports on advances in mathematical models of observer-ensemble performance in narrow-field- of-view visual search and target discrimination for ground vehicles in natural terrain. Three developments are presented. We show that the distribution of search time follows a log normal distribution. We show that search outcome is the result of a race between scene parsing and target detection. Scene parsing guides and focuses search, but also leads to quitting without detection. Quitting is not simply the consequence of having exhausted the supply of suspect locations. We present a refined target signature metric and computational method that emulates human perceptual organization of the target into component regions. This is significant not only because it improves the ease-of-use and reduces subjective user input, but also because it is potentially applicable to thermal images. The refined metric provides reasonably accurate prediction of probability of detection for cued detection and uncued search experiments., Presented at the Ground Target Modeling and Validation Conference (13th) held in Houghton, MI on 5-8 Aug 2002. Published in the Proceedings of the Ground Target Modeling and Validation Conference (13th), 247-256, 2002. This article is from ADA459530 Proceedings of the Ground Target Modeling and Validation Conference (13th) Held in Houghton, MI on 5-8 August 2002

In an earlier study, we described a method to create a parsing lexicon from semantic-based lexicon using manual rules. This paper describes an automated mapping methodology for the same purpose. Our approach maps lexical entries in a large LCS-based repository of semantically classified verbs to their corresponding syntactic patterns automatically. We evaluate the accuracy and coverage of this lexicon using LDOCE syntactic codes as a gold standard. We show that this lexicon is comparable to the hand-generated Minipar lexicon (i.e., similar recall and precision values). We also present the effects of using such a lexicon on the parser performance. The advantage of automating the process is that the same technique can be applied directly to lexicons we have for other languages, for example, Arabic, Chinese, and Spanish. The results indicate that our method will help us generate parsing lexicons which can be used by a broad-coverage parser that runs on different languages., Additional rept. UMIACS-TR-2002-32

We describe the design of an MT system that employs transfer rules induced from parsed bitexts and present evaluation results. The system learns lexico-structural transfer rules using syntactic pattern matching, statistical co-occurrence and errordriven filtering. In an experiment with domainspecific Korean to English translation, the approach yielded substantial improvements over three baseline systems. In this paper, we describe the design of an MT system that employs transfer rules induced from parsed bitexts and present evaluation results for Korean to English translation. Our approach is based on lexico-structural transfer (Nasr et. al., 1997), and extends recent work reported in (Han et al., 2000) about Korean to English transfer in particular. Whereas Han et al. focus on high quality domainspecific translation using handcrafted transfer rules, in this work we instead focus on automating the acquisition of such rules. The proposed approach is inspired by example based machine translation (EBMT; Nagao, 1984; Sato and Nagao, 1990; Maruyama and Watanabe, 1992) and is similar to the recent works of (Meyers et al., 1998) and (Richardson et al., 2001) where transfer rules are also derived after aligning the source and target nodes of corresponding parses. However, while (Meyers et al., 1998) and (Richardson et al., 2001) only consider parses and rules with lexical labels and syntactic roles, our approach uses parses containing any syntactic information provided by parsers (lexical labels, syntactic roles, tense, number, person, etc.), and derives rules consisting of any source and target tree sub-patterns matching a subset of the parse features. A more detailed description of the differences can be found in (Lavoie et. al., 2001).

The parsing community has long recognized the importance of lexicalized models of syntax. By contrast, these models do not appear to have had an impact on the statistical NLG community. To prove their importance in NLG, we show that a lexicalized model of syntax improves the performance of a statistical text compression system, and show results that suggest it would also improve the performances of an MT application and a pure natural language generation system.

This final technical report summarizes research conducted by Veridian Engineering and Cycorp, Inc. to assess the feasibility of leveraging the combined capabilities of the Intelligence Analyst Associate (IAA), an information extraction (IE) system, and the Cyc Knowledge Base (KB), a very large knowledge base, for monitoring domains of interest to intelligence analysts This research examined mechanisms to help alleviate the textual data overload that intelligence analysts experience. The IAA system has capabilities for processing large volumes of unstructured text, extracting information relevant to intelligence analysts, such as entities and simple events, storing the extracted information in a structured database, and enabling the use of analysis and visualization tools. By utilizing the Cyc KB, more intelligent processing using the context of the documents and that of the analysts' persistent knowledge bases to automatically generate new information and knowledge was accomplished. The inheritance feature of the Cyc KB ontological hierarchies provides a strong benefit in the efficient representation of knowledge. It was also shown that many of the information extraction tasks have interdependencies and that there is an advantage to accomplishing them in a KE using inference.

This paper describes a draft of visual notation for meta-programming. The main suggestions of this work include specialized data structures (lists, tuples, trees), data item associations that provide for creation of arbitrary graphs, visualization of data structures and data flows, graphical notation for pattern matching (list, tuple, and tree patterns, graphical notation for context free grammars, streams), encapsulation means for hierarchical rules design, two-dimensional data-flow diagrams for rules, visual control constructs for conditionals and iteration, default mapping results to reduce real-estate requirements for diagrams, and dynamic data attributes. Two-dimensional data flow diagrams improve readability of a meta-program. The abstract syntax type definitions for common programming languages and related default mappings (parsing and de-parsing) provide for a pracically feasible reuse of those components., Pub. in Proceedings of the 2001 Monterey Workshop entitled "Engineering Automation for Software Intensive System Integration" "Sponsored by DARPA, ONR, ARO and AFOSR", pp: 50-61, Monterey, CA, 2001

Syntactic information potentially plays a much more important role in question answering than it does in information retrieval. The aim of the experiment described in this paper is to study the impact of a particular approach for using syntactic information on question answering effectiveness. The TREC-9 QA track data are used in the evaluation. Our results indicate that a combination of syntactic information with heuristics for ranking potential answers can perform about 10% better than the ranking heuristics on their own.

Corpora of phrase-structure-annotated text, or treebanks, are useful for supervised training of statistical models for natural language processing, as well as for corpus linguistics. Their primary drawback, however, is that they are very time-consuming to produce. To alleviate this problem, the standard approach is to make two passes over the text: first, parse the text automatically, then correct the parser output by hand. In this paper we explore three questions: How much does an automatic first pass speed up annotation? Does this automatic first pass affect the reliability of the final product? What kind of parser is best suited for such an automatic first pass? We investigate these questions by an experiment to augment the Penn Chinese Treebank [15] using a statistical parser developed by Chiang [3] for English. This experiment differs from previous efforts in two ways: first, we quantify the increase in annotation speed provided by the automatic first pass (70 100%); second, we use a parser developed on one language to augment a corpus in an unrelated language., Presented at the Human Language Technology Conference (HLT 2001) held in San Diego, CA on 18-21 Mar 2001. Pub. in the Proceedings of the Human Language Technology Conference (HLT 2001), 2001. Sponsored in part by grant NSF SBR-89-20230-15.

This paper introduces GLARF, a framework for predicate argument structure. We report on converting the Penn Treebank II into GLARF by automatic methods that achieved about 90% precision/recall on test sentences from the Penn Treebank. Plans for a corpus of hand-corrected output extensions of GLARF to Japanese and applications for MT are also discussed., Presented at the ACL/EACL Workshop on Sharing Tools and Resources for Research and Education, held in Toulouse, France, on 7 Jul 2001. Published in the Proceedings of the ACL/EACL Workshop on Sharing Tools and Resources for Research and Education, p51-58, 2001. Prepared in cooperation with Monmouth University, West Long Branch, NJ. Sponsored in part by Defense Advanced Research Projects Agency (DARPA), and by the National Science Foundation (NSF), grant no. IIS-0081962.

Stochastic context-free grammars (SCFGs) are often used to represent the syntax of natural languages. Most algorithms for learning them require storage and repeated processing of a sentence corpus. The memory and computational demands of such algorithms are illsuited for embedded agents such as a mobile robot. Two algorithms are presented that incrementally learn the parameters of stochastic context-free grammars as sentences are observed. Both algorithms require a fixed amount of space regardless of the number of sentence observations. Despite using less information than the inside-outside algorithm, the algorithms perform almost as well.

Many corpus-based natural language processing systems rely on using large quantities of annotated text as their training examples. Building this kind of resource is an expensive and labor-intensive project. To minimize effort spent on annotating examples that are not helpful the training process., recent research efforts have begun to apply active learning techniques to selectively choose data to be annotated. In this work, we consider selecting training examples with the it tree-entropy metric. Our goal is to assess how well this selection technique can be applied for training different types of parsers. We find that tree-entropy can significantly reduce the amount of training annotation for both a history-based parser and an EM-based parser. Moreover, the examples selected for the history-based parser are also good for training the EM-based parser, suggesting that the technique is parser independent., Additional report no. UMIACS-TR-2001-40. Supported in part by NSF under Contract IR-9712068 and DARPA under Contract N66991-97-C-8540.

Tools for automatic program analysis promise to improve programmer productivity by searching and summarizing large bodies of code. However, the phenomenon of aliasing different names being used to refer to the same data reduces the effectiveness of simple textual analyses. This dissertation describes the design of a system, Ajax, that addresses this problem by using semantics-based program analysis as the basis for a number of different tools to aid Java programmers. To enable the construction of many tools, Ajax imposes a clean separation between analysis engines that produce alias information and tools that consume it. Analyses are treated as "black boxes" satisfying a simple, formal specification given in terms of the semantics of Java bytecode. Knowing only this specification, one can build many different tools with only a small amount of code. The thesis explores the flexibility and efficiency of the design by describing the construction and evaluation of several different tools: tools to find dead code, resolve Java virtual method calls, statically check Java downcasts, search for accesses to objects, and build object models. To support these tools, Ajax includes a novel static analysis engine for Java called SEMI, based on type inference with polymorphic recursion. SEMI provides fully context sensitive analysis of large programs. Using SEMI with the downcast checking tool, Ajax can prove the safety of more than 50% of the downcast instructions in some real-life Java programs, such as Sun's bytecode disassembler and the JavaCC parser generator. Ajax is the first system to address this particular task. One of the key goals of this thesis is to study issues bearing on the practical utility of static analysis tools for programmers. This document describes some of the challenges involved in building an analysis system for off-the-shelf Java applications, and suggests some possible avenues for future research., Sponsored in part by the National Science Foundation under Grant No., CCR9523972.

For the past three decades, the Department of Defense (DoD) has used the U.S. Message Text Format (USMTF) as the primary means to exchange information and to achieve interoperability between joint and coalition forces. To more effectively exchange and share data, the Defense Information Systems Agency (DISA), the lead agency for the USMTF, is actively engaged in extending the USMTF standard with a new data sharing technology called Extensible Markup Language (XML). This work translates and synthesizes Air Tasking Order (ATO) data messages written in XML into a three-dimensional (3D) air attack plan within a virtual environment through the use of the Virtual Reality Modeling Language (VRML).

We have made a number of advances under this grant. We have created what is currently the most accurate parser for parsing into Penn-tree-bank-style trees; a program that identifies the antecedents of pronouns with 85% accuracy; a program that assigns function tags to parse text with 85% accuracy; a program that assigns referents to full noun phrases with 65% accuracy; very efficient parsers that explore very few constituents that do not appear in the final parse; and programs that discover semantic information about words from unlabeled text. Furthermore, all these programs work by statistical means.

As electronic collections become larger and more numerous, systems capable of working with very large collections will be more and more in demand. On the other hand, computer main memory is relatively limited and constrained compared to the amount of data in a large collection. The requirement for larger memory while building big databases can sometimes make this resource a bottleneck for an information indexing system. INQUERY is a state-of-the-art, widely used, full-text information retrieval system. The INQUERY document indexing system consists of two main operations: parsing and merging. The subsystem responsible for parsing is called the Parser. It creates partial inverted lists by scanning, lexically analyzing, and inverting documents. A partial inverted list contains document entries for a subset of the documents in the collection. It must be combined with other partial inverted lists for the same term to create a final inverted list for the document collection. The Parser buffers partial inverted lists in main memory and flushes them to intermediate files when the buffer is full. The subsystem responsible for merging is called the Merger. After all of the documents have been parsed, the Merger combines the intermediate files to produce the final inverted lists for the collection. The aim of this project is to solve the efficiency and scalability problem of the Merger for the INQUERY indexing system. The speed performance of the old Merger (merge_btl) degrades significantly when used in building big databases under tight memory space limitations. The authors have found a better solution by using a hierarchical merge approach. Timing tests on the new Merger indicates that merge time can be significantly reduced. Hierarchical merge nicely solves the problem of scalability and greatly improves the efficiency of building very large databases for information retrieval systems., Sponsored in part by the National Science Foundation, Library of Congress, and Department of Commerce under cooperative agreement no. EEC-9209623.

This paper describes a refinement to our procedure for porting lexical conceptual structure into new languages. Specifically we describe a two-step process for creating candidate thematic grids for Mandarin Chinese verbs, using the English verb heading the VP in the subdefinitions to separate senses, and roughly parsing the verb complement structure to match to our thematic structure templates. The procedure is part of a larger process of creating a usable lexicon for interlingual machine translation from a large on-line resource with both too much and too little information necessary for our system., Report No., CS-TR-3911.

A new statistical parser has been developed which works on unconstrained newspaper text with an 89% success rate. It trains in minutes and its success is the highest in the field so far. A new robust parsing technology called "supertagging" was developed based on lexicalized tree-adjoining grammars (LTAG). This parser gives a very fine grain analysis and achieves a 93% success rate for assigning correct supertags to each word. This "almost parsing" becomes actual full parsing in many application domains. New technologies for automated entity based summarization of newspaper articles based on the conference technology developed earlier.

We continued our project on the IOA language and toolset, which are designed to support our formal approach to distributed system design and analysis. The design of the IOA language is substantially complete, and appears in a language manual on the web. This quarter, work continued on the development of tools for the IOA language; our toolset will include a parser and static semantic checker, composition routine, support for levels of abstraction interfaces with theorem provers and model checkers, a simulator, and a code generator for real distributed code.

The Crisis Action Message Analyzer (CAMA) is a text extraction system for Army logistics teleconferencing messages. CAMA uses natural language understanding (NLU) techniques to extract the information from free text messages that is important to a logistics action officer.

The Natural Language Processing (NLP) track was organized for the first time at TREC-5 to provide a more focused look at how NLP techniques can improve performance in information retrieval (IR). The intent was to see if the NLP techniques available today are mature enough to have an impact on IR, and whether they offer an advantage over purely quantitative methods. TREC-5 also was the place to try more expensive and more risky solutions than those used in main TREC evaluations. This NLP track demonstrated that NLP techniques have a solid but limited impact on the quality of text retrieval, particularly precision. Techniques aimed at producing higher quality queries, (e.g., query expansion, constraints) appear to be more effective than those aimed primarily at obtaining improved indexing of database documents. More work is needed before substantial gains can be seen, including the use of more advanced and expensive semantic analysis techniques. Figure 2 summarizes the NLP techniques that have been tried in information retrieval, and what their potential might be for improving retrieval precision. This chart was discussed at the NLP track workshop on the last day of TREC-5. The consensus was that NLP techniques that show particular promise in relatively small-scale track evaluations should be transferred to main evaluations as soon as practical., Presented at the Text Retrieval Conference (TREC-5) (5th) held in Gaithersburg, MD, on 20-22 Nov 1996. The original document contains color images.

The VTST project developed a set of Built-In-Self-Test (BIST) methodologies and implemented them in the VTST Computer Aided Design (CAD) toolset. These test methodologies include a pseudo- exhaustive parallel BIST technique that utilizes an efficient test signal reduction method for combinational circuits based on Dr. Chen's research. This technique reduces the size of the test pattern generator (TPG) and the number of test patterns required for a given Circuit Under Test (CUT). Dr. Chen's method was extended to include methods for testing storage elements, i.e., sequential circuits. The VTST toolset includes a non-scan circular BIST method, full and partial-scan methodologies, and circular BIST combined with pseudo-partial scan. Programs are included for fault simulation, partitioning circuits into subcircuits to improve fault coverage, removing redundant faults, synthesizing BIST circuits, and automatically inserting the BIST circuits into the original circuit. The VTST toolset interfaces with LSI Logic's CMDE CAD toolset, generating BlST'ed circuits in LSI's NDL format. A VHDL parser is included that allows VHDL designs to be input to VTST; VHDL output can also be generated. The tools are hosted on a Sun workstation and permit concurrent engineering use on multiple machines. Several test circuits were processed to verify correct operation.

This document is a guide to a set of programs that can be used to submit GSE2.O formatted waveform requests to an autoDRM site and automatically parse the email responses. Given an event time and location, travel times are used to compute request-time-windows for a list of stations. Waveform data received in GSE2.0 format are converted to CSS3.0 format and stored in a user-defined directory structure. Multiple requests for separate events can be submitted simultaneously. The status of multiple requests can be monitored through the system's log files. A GUI to the log files is included.

The goal of this research was to provide the groundwork for an investigation of an approach to domain independent semantic processing; the combination of a principle based parser (PBP) with a semantically enhanced machine readable dictionary (MRD). The parser is an implementation of Chomsky's Government-Binding theory and therefore provides complete syntactic coverage. The coverage of a parsing system is, however, ultimately a function of the size and richness of its lexicon. To provide both size and richness, the lexicon for the system was extracted from Longman's Dictionary of Contemporary English and semantically enhanced using Roger's International Thesaurus. Increased lexical richness increases system coverage but it may decrease the efficiency of the parser. Therefore, this research investigated the impact of using an MRD as the lexicon for a PBP. The results show that an MRD can indeed be used with a PBP though the larger, more ambiguous lexicon requires controls in the parser to avoid producing a large forest of candidate parse trees. With such controls, the impact of the larger lexicon becomes no greater for a PBP than for a traditional phrase structure grammar (ex., ATN, APSG) dealing with lexical ambiguity.

The FORTRAN language has been and continues to be one of the most heavily used languages for implementing complex numerical algorithms. It is extremely efficient, and the straightforward constructs of the language allow today's FORTRAN compilers to take full advantage of the most novel parallel and vector computers. Many of these algorithms require large data sets to be read. This is the one task in which FORTRAN is somewhat lacking. While the main computation task should be left in FORTRAN, parsing tasks should be performed by applications with greater character stream access. Accessing and processing this character stream that is formed while the file is being read is known as parsing. This paper describes the tools available on most UNIX systems which can produce very fast parsers, the underlying methods employed by these tools, and ways these tools can be integrated with FORTRAN numerical solvers. (AN)

This paper provides a quick summary of our technical approach, which has been developing since 1991 and was first fielded in MUC-3. First a quick review of what is new is provided, then a walk through of system components. Perhaps most interesting is out analysis, following the walk through, of what we learned through MUC-6 and of what directions we would take now to break the performance barriers of current information extraction technology., Presented at the Message Understanding Conference (6th) (MUC-6), held in Columbia, MD on 6-8 November 1995. Pub. in the Proceedings of the Message Understanding Conference (6th) (MUC-6), 1995.

This report is a user's manual for the TRAINs-95 parsing system. An accompanying report describes the grammar used in TRAINs-95, and the robust speech act interpretation system, which takes the chart and produces a series of speech acts that best characterize it. The parser is based on the bottom-up parser described in Natural Language Understanding, Second Ed. (Allen, 1994, Chapters 3,4, and 5). It uses the same formats for the grammar and the lexical entries, and the same basic bottom-up algorithm. There are a number of extensions beyond the basic system described in the book, each of which will be discussed in this report, including *support for parsing word lattices *best-first parsing using context-free probabilistic rules *incremental (word by word) parser with backup for corrections *hierarchical feature values and extended unification options *a hierarchical lexicon entry format that simplifies defining large lexicons procedural attachment to Chart actions

We are developing a theory of parsing and generation which will bridge between language-multimedia surface structure and internal meaning structures. The idea is that a system could receive a variety of perceived data and this could include spoken and/or typed natural language, visual information, tactile information and possibly other inputs. It will then use a new kind of multimedia grammar to parse those inputs and discover their associated structure. Finally, it will use the discovered structure to translate the input into meaning structures that can be used internally for understanding an input and deciding on appropriate answers. Our theory at this point is bidirectional. Specifically, the same algorithm used to parse inputs can be used to generate Outputs. If a meaning structure is to be expressed to the user, the system must find the set of language constructs that will express the target meaning. This involves a parsing-like process in which the structure of the meaning is analyzed and the correct rules needed to express the meaning are discovered. Here those rules then lead to a set of multimedia language constructs that can be assembled to express the originally given meaning. The theory includes the specification of a set of operators 01, 02, 03,... each with a syntactic component, a semantic component, and some applicability criteria. The parsing algorithm(which can also be used for generation) searches for the sequence of operators 01 that will account for the observed surface structure. Their semantic parts then are invoked to find the target meaning. A key to the research is to find a representation for the operators that will enable fast and efficient processing.

Modeling the morphological structure of natural languages in terms of a nondeterministic finite-state automaton is shown to be inadequate in its handling of some common natural language phenomena. We show that a two-tape nondeterministic automaton is capable of handling these phenomena. The modeling is improved by the specification of a new type of automaton, the preset two-head automaton, which we argue is equivalent in expressive power to a linear context-free grammar. We discuss the operation of a parser which implements the improved model.

Our project stated the following broad goals: (a) to design a practical tool capable of automating major aspects of programming-essentially, a generalization of YACC and MACSYMA to facilitate implementation of a wide class of complex nonnumerical algorithms (in addition to parsing); (b) to design and implement complexity based specification languages; (c) to integrate problem specification, program design, verification, and analysis within a single unified framework; (d) to design and efficiently implement pattern directed rule systems for semantic analysis; and (3) to make it easier to teach and understand algorithms and software engineering.