Search

An Earley parser is a top-down parsing technique that is capable of parsing arbitrary context-free grammars. We present a functional implementation of an Earley parser verified using the interactive theorem prover Isabelle/HOL. Our formalization builds upon Cliff Jones' extensive, refinement-based paper proof. We implement and prove soundness and completeness of a functional recognizer modeling Jay Earley’s original imperative implementation and extend it with the necessary data structures to enable the construction of parse trees following the work of Elizabeth Scott. Building upon this foundation, we develop a functional parser and prove its soundness. We round off the paper by providing an informal argument and empirical data regarding the running time and space complexity of our implementation.

Traditionally, a grammar defining the syntax of a programming language is typically both context free and unambiguous. However, recent work suggests that an attractive alternative is to use ambiguous grammars,thus postponing the task of resolving the ambiguity to the end user. If all programs accepted by an ambiguous grammar can be rewritten unambiguously, then the parser for the grammar is said to be resolvably ambiguous. Guaranteeing resolvable ambiguity statically---for all programs---is hard, where previous work only solves it partially using techniques based on property-based testing. In this paper, we present the first efficient, practical, and proven correct solution to the statically resolvable ambiguity problem. Our approach introduces several key ideas, including splittable productions, operator sequences, and the concept of a grouper that works in tandem with a standard parser. We prove static resolvability using a Coq mechanization and demonstrate its efficiency and practical applicability by implementing and integrating resolvable ambiguity into an essential part of the standard OCaml parser.

Traditionally, a grammar defining the syntax of a programming language is typically both context free and unambiguous. However, recent work suggests that an attractive alternative is to use ambiguous grammars,thus postponing the task of resolving the ambiguity to the end user. If all programs accepted by an ambiguous grammar can be rewritten unambiguously, then the parser for the grammar is said to be resolvably ambiguous. Guaranteeing resolvable ambiguity statically---for all programs---is hard, where previous work only solves it partially using techniques based on property-based testing. In this paper, we present the first efficient, practical, and proven correct solution to the statically resolvable ambiguity problem. Our approach introduces several key ideas, including splittable productions, operator sequences, and the concept of a grouper that works in tandem with a standard parser. We prove static resolvability using a Coq mechanization and demonstrate its efficiency and practical applicability by implementing and integrating resolvable ambiguity into an essential part of the standard OCaml parser.

Traditionally, a grammar defining the syntax of a programming language is typically both context free and unambiguous. However, recent work suggests that an attractive alternative is to use ambiguous grammars,thus postponing the task of resolving the ambiguity to the end user. If all programs accepted by an ambiguous grammar can be rewritten unambiguously, then the parser for the grammar is said to be resolvably ambiguous. Guaranteeing resolvable ambiguity statically---for all programs---is hard, where previous work only solves it partially using techniques based on property-based testing. In this paper, we present the first efficient, practical, and proven correct solution to the statically resolvable ambiguity problem. Our approach introduces several key ideas, including splittable productions, operator sequences, and the concept of a grouper that works in tandem with a standard parser. We prove static resolvability using a Coq mechanization and demonstrate its efficiency and practical applicability by implementing and integrating resolvable ambiguity into an essential part of the standard OCaml parser.

Traditionally, a grammar defining the syntax of a programming language is typically both context free and unambiguous. However, recent work suggests that an attractive alternative is to use ambiguous grammars,thus postponing the task of resolving the ambiguity to the end user. If all programs accepted by an ambiguous grammar can be rewritten unambiguously, then the parser for the grammar is said to be resolvably ambiguous. Guaranteeing resolvable ambiguity statically---for all programs---is hard, where previous work only solves it partially using techniques based on property-based testing. In this paper, we present the first efficient, practical, and proven correct solution to the statically resolvable ambiguity problem. Our approach introduces several key ideas, including splittable productions, operator sequences, and the concept of a grouper that works in tandem with a standard parser. We prove static resolvability using a Coq mechanization and demonstrate its efficiency and practical applicability by implementing and integrating resolvable ambiguity into an essential part of the standard OCaml parser.

Parser combinators are a well-known mechanism used for the compositional construction of parsers, and have shown to be particularly useful in writing parsers for rich grammars with data-dependencies and global state. Verifying applications written using them, however, has proven to be challenging in large part because of the inherently effectful nature of the parsers being composed and the difficulty in reasoning about the arbitrarily rich data-dependent semantic actions that can be associated with parsing actions. In this paper, we address these challenges by defining a parser combinator framework called Morpheus equipped with abstractions for defining composable effects tailored for parsing and semantic actions, and a rich specification language used to define safety properties over the constituent parsers comprising a program. Even though its abstractions yield many of the same expressivity benefits as other parser combinator systems, Morpheus is carefully engineered to yield a substantially more tractable automated verification pathway. We demonstrate its utility in verifying a number of realistic, challenging parsing applications, including several cases that involve non-trivial data-dependent relations.

Traditionally, a grammar defining the syntax of a programming language is typically both context free and unambiguous. However, recent work suggests that an attractive alternative is to use ambiguous grammars,thus postponing the task of resolving the ambiguity to the end user. If all programs accepted by an ambiguous grammar can be rewritten unambiguously, then the parser for the grammar is said to be resolvably ambiguous. Guaranteeing resolvable ambiguity statically---for all programs---is hard, where previous work only solves it partially using techniques based on property-based testing. In this paper, we present the first efficient, practical, and proven correct solution to the statically resolvable ambiguity problem. Our approach introduces several key ideas, including splittable productions, operator sequences, and the concept of a grouper that works in tandem with a standard parser. We prove static resolvability using a Coq mechanization and demonstrate its efficiency and practical applicability by implementing and integrating resolvable ambiguity into an essential part of the standard OCaml parser.

This is an industrial experience report on a large semi-automated migration of legacy test code in C and C++. The particular migration was enabled by automating most of the maintenance steps. Without automation this particular large-scale migration would not have been conducted, due to the risks involved in manual maintenance (risk of introducing errors, risk of unexpected rework, and loss of productivity). We describe and evaluate the method of automation we used on this real-world case. The benefits were that by automating analysis, we could make sure that we understand all the relevant details for the envisioned maintenance, without having to manually read and check our theories. Furthermore, by automating transformations we could reiterate and improve over complex and large scale source code updates, until they were “just right.” The drawbacks were that, first, we have had to learn new metaprogramming skills. Second, our automation scripts are not readily reusable for other contexts; they were necessarily developed for this ad-hoc maintenance task. Our analysis shows that automated software maintenance as compared to the (hypothetical) manual alternative method seems to be better both in terms of avoiding mistakes and avoiding rework because of such mistakes. It seems that necessary and beneficial source code maintenance need not to be avoided, if software engineers are enabled to create bespoke (and ad-hoc) analysis and transformation tools to support it.

This is an industrial experience report on a large semi-automated migration of legacy test code in C and C++. The particular migration was enabled by automating most of the maintenance steps. Without automation this particular large-scale migration would not have been conducted, due to the risks involved in manual maintenance (risk of introducing errors, risk of unexpected rework, and loss of productivity). We describe and evaluate the method of automation we used on this real-world case. The benefits were that by automating analysis, we could make sure that we understand all the relevant details for the envisioned maintenance, without having to manually read and check our theories. Furthermore, by automating transformations we could reiterate and improve over complex and large scale source code updates, until they were “just right.” The drawbacks were that, first, we have had to learn new metaprogramming skills. Second, our automation scripts are not readily reusable for other contexts; they were necessarily developed for this ad-hoc maintenance task. Our analysis shows that automated software maintenance as compared to the (hypothetical) manual alternative method seems to be better both in terms of avoiding mistakes and avoiding rework because of such mistakes. It seems that necessary and beneficial source code maintenance need not to be avoided, if software engineers are enabled to create bespoke (and ad-hoc) analysis and transformation tools to support it.

This paper addresses these research questions: (1) What are the main ideas presented in the published articles (2005–2020) on structural ambiguity resolution in language processing? (2) What are the main venues for unveiling research on structural ambiguity resolution in language processing? For that, a systematic review is performed, which reports on the eight most relevant studies. It is found the investigations into the topic of interest are conducted across multidisciplinary areas and primarily in the European institutions and the US. This research is circulated in journals, which are peer-reviewed and indexed by Scopus, Web of Science, and other databases. The other major finding is that psychophysical tests are more popular in the field, and reasons for that are explained. The polarity of results on syntactic disambiguation leaves room for much to be discovered.

Parsing is the process of analysing an input string in order to extract a structured representation of its content (a syntax tree) with respect to a specific language. In the thesis, we focus on parsing formal languages, such as programming or markup languages — as opposed to natural spoken languages. Unlike natural languages, formal languages are never ambiguous: there is only a single correct interpretation of the input. Parsing is a pervasive activity: every time a source file must be turned into executable code, a parser is required. Similarly, parsers are used to convert input files into relevant data structures. It is fair to say that most programs include a parser — sometimes many. As such, making parsers easier to write, use, and modify is a broadly beneficial endeavour. This thesis is concerned with the limitations of currently available parsing systems, and how to overcome them. In particular, we show how to develop a simple yet expressive notation that can be easily extended, and build upon this basis to add context-sensitive parsing to the parsing system, robust support for infix expression (avoiding expressiveness and performance issues relating to associativity selection) as well as many more expressiveness and usability features — such as permissive parsing and debugging tools., (FSA - Sciences de l'ingénieur) -- UCL, 2019

Red Shift is a new design pattern for implementing parsers. The pattern draws ideas from traditional shift-reduce parsing as well as procedural PEG parsers. Red Shift parsers behaves like shift-reduce parsers, but eliminate ambiguity by always prioritizing reductions over shifts. To compensate the resulting lack of expressivity, reducers are not simple reduction rules but full-blown procedures written in a general-purpose host language. I found many advantages to this style of parser. In particular, we can generate high-quality error messages more easily; and compose different style of parsers. I also speculate about how Red Shift parsers may improve partial compilation in the context of an IDE.

Supervisor:Associate Prof. Nguyen Minh Le, School of Information Science, Master, identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/12985

The project's main focus was on tractable inference and learning of probabilistic representations, which are essential for large-scale abductive inference applications. We also developed novel inference techniques based on lifting, sampling, and more efficient processing of evidence. We continued to extend Alchemy 2.0, an open-source toolkit for Markov logic, and Alchemy Lite, an implementation of Tractable Markov Logic (TML). We developed parameter and structure learning algorithms for sum-product networks and, building on TML, we substantially improved two tractable probabilistic-logical formalisms: relational sum-product networks and tractable probabilistic knowledge bases. Based on sum-product networks, we worked towards formalisms for tractable probabilistic programming. We worked on symmetrybased inference and learning and developed novel model classes that exploit invariances of the data with respect to group operations. A novel model for Biomedical event extraction based on MLNs that leverages the power of support vector machines (SVMs) to handle highdimensional features was proposed and applied to the problem of event extraction. We developed structured prediction models by introducing novel forms of regularization. We continued to apply Markov logic networks to the problem of textual inference and conducted extensive experiments on benchmark datasets. We further improved GraphLab, our large-scale parallel machine learning framework. We investigated novel approaches to activity and plan recognition, and showed that Markov logic is capable of fusing visual and language evidence of the activities under consideration.

This technical note provides a brief description of a Java library for Arabic natural language processing (NLP) containing code for training and applying the Arabic NLP system described in the paper A Cross-Task Flexible Transition Model for Arabic Tokenization, Affix Detection, Affix Labeling, POS Tagging, and Dependency Parsing by Stephen Tratz presented at the Statistical Parsing of Morphologically Rich Languages (SPMRL) workshop held in Seattle in conjunction with the Empirical Methods in Natural Language Processing (EMNLP) conference of October 2013. The system is capable of clitic separation, inflectional affix identification and labeling, part-of-speech tagging, and dependency parsing for Arabic. The code, which is extended from previously released graduate student code, also supports English part-of-speech tagging, dependency parsing, and semantic disambiguation tasks. In general, the code library is expected to be of most value to natural language processing researchers., The original document contains color images.

Text files are often used to store tabulated data and user-modifiable inputs for scientific modeling. This report presents a set of functions, written in C++, that can be used to read, write, and parse text files., The original document contains color images.

We propose using deep learning as the workhorse of a cognitive architecture. We show how deep learning can be leveraged to learn representations, such as a hierarchy of analogical schemas, from relational data. Our view drives some desiderata of deep learning, particularly modality independence and the ability to make top-down predictions. Finally, we consider the problem of how relational representations might be learned from sensor data that is not explicitly relational., To be presented at the AAAI Workshop on Learning Rich Representations from Low-Level Sensors, Bellvue, WA, July 15, 2013. The original document contains color images.

The goal of the TREC 2012 Medical Records Track was to search medical record documents to identify patients as possible candidates for clinical studies based on diagnosis, age, and other attributes. For TREC 2012, the Oregon Health & Science University (OHSU) group experimented with both manual and automated techniques. We used a derivative of Lucene to build an interactive retrieval system that can process queries in one of two ways. Users can manually specify Boolean queries whose terms may include words as well as ICD-9 codes. Alternatively, the system features an automated query parser that transforms free-text queries into structured Boolean queries. The query parser is built on top of MetaMap and the UMLS Metathesaurus. We submitted both automatic runs (which relied solely on the automated query parser) as well as manual runs consisting of queries built by an expert clinician. Overall, our automated query parser performed below the mean of other groups, although there were individual topics for which it performed very well. This irregular performance was in part due to our parser's tendency to over-specify queries, leading to reduced recall. There were, however, several topics for which our parser performed very well, suggesting that our fundamental approach has merit. In contrast, our manual runs performed very well, scoring second-best among official manual runs. With further modification of the manual queries, we were able to achieve even better performance. Query of electronic health records for the use case of identifying patients as candidates for clinical studies still requires manual query development, at least until better automated methods can be developed that outperform them., Presented at the Twenty-First Text REtrieval Conference (TREC 2012) held in Gaithersburg, Maryland, November 6-9, 2012. The conference was co-sponsored by the National Institute of Standards and Technology (NIST) the Defense Advanced Research Projects Agency (DARPA) and the Advanced Research and Development Activity (ARDA). U.S. Government or Federal Rights License

In this paper, we report our experiments at Ad-hoc task, Web Track 2012. In this year, we attempt to use new web parser with noise elimination. The Conditional Boolean BM25 was used as major ranking function. We also introduce Learning-To-Rank to combine multiple features together for ranking, but the performance was poor due to the low quality of training data., Presented at the Twenty-First Text REtrieval Conference (TREC 2012) held in Gaithersburg, Maryland, November 6-9, 2012. The conference was co-sponsored by the National Institute of Standards and Technology (NIST) the Defense Advanced Research Projects Agency (DARPA) and the Advanced Research and Development Activity (ARDA). U.S. Government or Federal Rights License

The system to Contextual Suggestion Track at TREC2012 includes information crawling and preprocessing, context filtering, user modeling, similarity computing and ranking, description generating. Some third party tool kits are used, such as URLPARSE. TF-IDF (term frequency-inverse document frequency) and cosine similarity is also used for building user models and computed similarities between users and candidate items., Presented at the Twenty-First Text REtrieval Conference (TREC 2012) held in Gaithersburg, Maryland, November 6-9, 2012. The conference was co-sponsored by the National Institute of Standards and Technology (NIST) the Defense Advanced Research Projects Agency (DARPA) and the Advanced Research and Development Activity (ARDA). U.S. Government or Federal Rights License

We present a simple but accurate parser which exploits both large tree fragments and symbol refinement. We parse with all fragments of the training set, in contrast to much recent work on tree selection in data-oriented parsing and tree-substitution grammar learning. We require only simple, deterministic grammar symbol refinement, in contrast to recent work on latent symbol refinement. Moreover, our parser requires no explicit lexicon machinery, instead parsing input sentences as character streams. Despite its simplicity, our parser achieves accuracies of over 88% F1 on the standard English WSJ task, which is competitive with substantially more complicated state-of-the-art lexicalized and latent-variable parsers. Additional specific contributions center on making implicit all-fragments parsing efficient, including a coarse-to-fine inference scheme and a new graph encoding.

This paper describes a novel technique for incorporating syntactic knowledge into phrase-based machine translation through incremental syntactic parsing. Bottom-up and top-down parsers typically require a completed string as input. This requirement makes it difficult to incorporate them into phrase-based translation, which generates partial hypothesized translations from left-to-right. Incremental syntactic language models score sentences in a similar left-to-right fashion, and are therefore a good mechanism for incorporating syntax into phrase-based translation. We give a formal definition of one such linear-time syntactic language model, detail its relation to phrase-based decoding, and integrate the model with the Moses phrase-based translation system. We present empirical results on a constrained Urdu-English translation task that demonstrate a significant BLEU score improvement and a large decrease in perplexity., Presented at the Annual Meeting of the Association for Computational Linguistics (49th) held in Portland, Oregon, on June 19-24, 2011. Published in the Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, p620-631, June 2011. Sponsored in part by the National Science Foundation.

A system and method for simple network management protocol downtime calculator includes storing a log comprising a plurality of trap events from corresponding nodes in a subsystem in a network, the plurality of trap events comprising down events and up events, parsing the log to separate down events and up events, pairing down events with corresponding up events, the pairing including matching, for the at least one node in the subsystem, a down event having a severity level with an up event having the corresponding severity level, calculating subsystem downtime, and calculating operational availability of the subsystem. Additional features include identifying overlapping downtimes in the subsystem.

As the study and application of statistical machine translation (SMT) grows, progress is often circumscribed by a lack of data. The statistical models that govern statistical machine translation (SMT) engines rely on many large bilingual text corpora, each comprised of vast numbers of bilingual text segments. For certain languages, corpora already exist and help to power translation engines. Regrettably, this is not the case for every language the Army is interested in, making the creation or acquisition of such data a priority. To this end, a language expert in Dari and Pashto was hired, who collected, prepared, and ensured the quality of bilingual text. To explore ways in which to aid the expert, a variety of the steps performed by the expert and necessary to the process were automated. The hypothesis was that automation of selected processes would improve efficiency, measured in terms of both speed of production and quantity of data produced, even when time to correct automation-caused errors was accounted for. As predicted, the net result of introducing automation was an increase in both the rate of producing correct bilingual segments and the number produced. The implications of these results for improving larger bilingual data creation and acquisition efforts are discussed., The original document contains color images.

Written information for military purposes is available in abundance. Documents are written in many languages. The question is how we can automate the content extraction of these documents. One possible approach is based on shallow parsing (information extraction) with application specific combination of analysis results. One example of this, the ZENON research system, does a partial content analysis of some English, Dari, and Tajik texts. Another principal approach for content extraction is based on a combination of deep and shallow parsing with logical inferences on the analysis results. In the project "Multilingual content analysis with semantic inference on military relevant texts" (mIE) we followed the second approach. In this paper, we present the results of the mIE project. First, we briefly contrast the ZENON project to the mIE project. In the main part of the paper, the mIE project is presented. After explaining the combined deep and shallow parsing approach with Head-driven Phrase Structured Grammars, the inference process is introduced. Then we show how background knowledge (WordNet, YAGO) is integrated into the logical inferences to increase the extent, quality, and accuracy of the content extraction. The prototype also is presented. The presentation includes briefing charts., Presented at the International Command and Control Research and Technology Symposium (ICCRTS 2011) (16th) held in Quebec City, Canada, on 21-23 June 2011. Published in the Proceedings of the 16th International Command and Control Research and Technology Symposium, June 2011.

The reliability of compilers, interpreters, and development environments for programming languages is essential for effective software development and maintenance. They are often tested only as an afterthought. Languages with a smaller scope, such as domain-specific languages, often remain untested. General-purpose testing techniques and test case generation methods fall short in providing a low-threshold solution for test-driven language development. In this paper we introduce the notion of a language-parametric testing language (LPTL) that provides a reusable, generic basis for declaratively specifying language definition tests. We integrate the syntax, semantics, and editor services of a language under test into the LPTL for writing test inputs. This paper describes the design of an LPTL and the tool support provided for it, shows use cases using examples, and describes our implementation in the form of the Spoofax testing language. This paper is a pre-print of: Lennart C. L. Kats, Rob Vermaas, Eelco Visser. Integrated Language Definition Testing. Enabling Test-Driven Language Development. In Kathleen Fisher, editor, Proceedings of the 26th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2011), ACM, 2010., Software Technology, Electrical Engineering, Mathematics and Computer Science

This dissertation presents research on techniques, methods, and tool support for domain-specific language engineering. Domain-specific language engineering is the discipline of designing, developing, and maintaining domain-specific programming languages. The focus of this thesis is the architecture of language workbenches their underlying technologies. Language workbenches are tools that make language engineering more efficient by providing an integrated development environment for language engineering tasks. In particular, we introduce the Spoofax language workbench, and describe its techniques for high-level, portable language definitions, language composition, interactive support for defining languages, and language testing. Our research focuses on three main themes: applying domain-specific languages for declarative specification of languages and IDEs; supporting declarative syntax definition for generating a parser-based, interactive development environment; and providing interactive meta-tooling support, exploring the application of modern IDE technology to DSL engineering., Software Technology, Electrical Engineering, Mathematics and Computer Science

The reliability of compilers, interpreters, and development environments for programming languages is essential for effective software development and maintenance. They are often tested only as an afterthought. Languages with a smaller scope, such as domain-specific languages, often remain untested. General-purpose testing techniques and test case generation methods fall short in providing a low-threshold solution for test-driven language development. In this paper we introduce the notion of a language-parametric testing language (LPTL) that provides a reusable, generic basis for declaratively specifying language definition tests. We integrate the syntax, semantics, and editor services of a language under test into the LPTL for writing test inputs. This paper describes the design of an LPTL and the tool support provided for it, shows use cases using examples, and describes our implementation in the form of the Spoofax testing language. This paper is a pre-print of: Lennart C. L. Kats, Rob Vermaas, Eelco Visser. Integrated Language Definition Testing. Enabling Test-Driven Language Development. In Kathleen Fisher, editor, Proceedings of the 26th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2011), ACM, 2010., Software Technology, Electrical Engineering, Mathematics and Computer Science

This dissertation presents research on techniques, methods, and tool support for domain-specific language engineering. Domain-specific language engineering is the discipline of designing, developing, and maintaining domain-specific programming languages. The focus of this thesis is the architecture of language workbenches their underlying technologies. Language workbenches are tools that make language engineering more efficient by providing an integrated development environment for language engineering tasks. In particular, we introduce the Spoofax language workbench, and describe its techniques for high-level, portable language definitions, language composition, interactive support for defining languages, and language testing. Our research focuses on three main themes: applying domain-specific languages for declarative specification of languages and IDEs; supporting declarative syntax definition for generating a parser-based, interactive development environment; and providing interactive meta-tooling support, exploring the application of modern IDE technology to DSL engineering., Software Technology, Electrical Engineering, Mathematics and Computer Science

Natural language understanding is a sub-field of natural language processing which builds automated systems to understand natural language. It is such an ambitious task that it sometimes is referred to as an AI-complete problem, implying that its difficulty is equivalent to solving the central artificial intelligence problem-making computers as intelligent as people. Despite its complexity, natural language understanding continues to be a fundamental problem in natural language processing in terms of its theoretical and empirical importance. In recent years, startling progress has been made at different levels of natural language processing tasks, which provides great opportunity for deeper natural language understanding. In this thesis, we focus on the task of semantic parsing which maps a natural language sentence into a complete, formal meaning representation in a meaning representation language. We present two novel state-of-the-art learned syntax-based semantic parsers using statistical syntactic parsing techniques motivated by the following two reasons. First, the syntax-based semantic parsing is theoretically well-founded in computational semantics. Second, adopting a syntaxbased approach allows us to directly leverage the enormous progress made in statistical syntactic parsing. The first semantic parser, SCISSOR, adopts an integrated syntactic-semantic parsing approach, in which a statistical syntactic parser is augmented with semantic parameters to produce a semantically-augmented parse tree (SAPT). This integrated approach allows both syntactic and semantic information to be available during parsing time to obtain an accurate combined syntactic-semantic analysis. The performance of SCISSOR is further improved by using discriminative reranking for incorporating non-local features. The second semantic parser, SYNSEM exploits an existing syntactic parser to produce disambiguated parse trees that drive the compositional semantic interpretation.

This report describes a design study carried out at the Computing Research Laboratory, New Mexico State University. The goal was to investigate the feasibility of creating a visual interpretation of the spoken messages passed among the crew of an Unmanned Aerial Vehicle (UAV). Because of the limited domain of UAV crew dialogs, it seemed possible to produce visual representations of their messages. These visualized messages could be used for communication among UAV crew members who do not speak the same language, and they could also visually verify any spoken communications. The following tasks were carried out by the research team: (1) a general analysis of how images could be used to represent dialogs; (2) a more specific analysis of dialogs and parse trees produced from experimental UAV dialogs; (3) participation in discussions and in a simulated flight as crew members while visiting researchers at AFRL, Mesa; (4) development of a set of icons and conventions to represent mission status and the form of crew member dialogs; (5) design of a prototype visualization system -- Chat2Pix; (6) implementation of the prototype using Visual Basic to run on Windows systems; (7) redesign of the prototype to display more structured information; and (8) implementation and delivery of a second version of the visualization system -- Chat2Pix2.

Process Coloring is an information-preserving, provenance-aware software system for computer malware detection and investigation. By tainting each application process with a distinct color and propagating the color to other processes or system objects along with system call operations, Process Coloring preserves the "provenance" of malware attacks (namely, "Through which process did a malware program infiltrate the system?"). Process Coloring enables three useful malware defense capabilities: (1) color-based malware detection, (2) color-based malware break-in point identification, and (3) color-based log partitioning. Implemented on top of a virtualization platform, Process Coloring achieves strong tamper-resistance as the logs generated by the protected (virtual) machine are stored and processed outside the machine under attack. Finally, Process Coloring can be integrated with techniques that track information flows inside a program. The resultant integrated system achieves better malware detection accuracy by eliminating false positive alerts, especially for client-side environments. This report gives an overview of the Process Coloring project and presents the design, implementation, and evaluation highlights in the research effort., The original document contains color images. Prepared in cooperation with North Carolina State University, Raleigh, NC.

Building a robust spoken dialogue system for a new application, task, or domain currently requires considerable effort, including substantial efforts in data collection, building language models, grammar/parser development, building a custom dialogue manager, and developing the connection to the system's "back-end" systems (e.g., a database query or knowledge based system). This project developed key parts of a technology base upon which spoken dialogue systems can be rapidly constructed for new domains. Our approach involves building generic components (i.e., ones that apply in any practical domain) for all stages of spoken dialogue understanding, and developing techniques for rapidly customizing the generic components to new domains.

Learning to read is an important skill for both children and adults, whether it takes place in their first language or their second language. According to the National Center for Educational Statistics 2003 Assessment (2007), 5% of adults (16 years and older) in the United States are functionally non-literate. Adults who enroll in literacy programs in the United States desire to improve reading skills for a variety of reasons. But resources are limited, as literacy programs often rely on volunteer tutors and variable funding sources. Computers are increasingly used to assist in the tutoring process. Improving the computer's ability to aid in this process with useful tools for instructors and students will allow students access to more reading materials and provide them with more opportunities to read. The primary goal for everyone is to increase reading and reading ability. For instructors, writing questions for reading comprehension exercises is time-consuming and difficult. The questions are only useful for a single text. Authoring tools such as Conduit's Dasher (1993), Half-baked Software's Hotpotatoes (2003-2007), and the University of Arizona's MaxAuthor (2007) make the task somewhat easier with tools for creating exercises, and more productive by means of allowing instructors to share exercises on the Internet. Reading comprehension is composed of several skill levels that work with various language or text chunks: awareness of phonemes, decoding skills, fluency vocabulary knowledge, grammar skills, and meta-learning skills. The goal of the project described in this report was to create a system that could automatically and accurately generate fact-based reading comprehension questions with expository text for teaching or using a specific look-back reading strategy. The project also aimed to use existing Natural Language programs and knowledge sources as well as implementing new ways to combine their output.

In this paper we describe our system, experiments and results from our participation in the Blog Track at TREC 2008. Dublin City University participated in the adhoc retrieval, opinion finding and polarised opinion finding tasks. For opinion finding, we used a fusion of approaches based on lexicon features, surface features and syntactic features. Our experiments evaluated the relative usefulness of each of the feature sets and achieved a significant improvement on the baseline., Presented at the Seventeenth Text REtrieval Conference (TREC 2008) held in Gaithersburg, MD on November 18-21, 2008. Sponsored in part by the National the Defense Advanced Research Projects Agency (DARPA) and the Advanced Research and Development Activity (ARDA). The original document contains color images.

In this paper we describe the TNO approach to large-scale polarity classification of the Blog TREC 2008 dataset. Our participation consists of the submission of the 5 baseline runs provided by NIST, for which we applied a multinomial kernel machine operating on character n-gram representations., Presented at the Text Retrieval Conference (17th), held in Gaithersburg, Maryland, on 18-21 November 2008. Sponsored in part by Defense Advanced Research Projects Agency (DARPA) and the Advanced Research and Development Activity (ARDA). The original document contains color images.

The GPS Toolkit (GPSTk) is an open source software project sponsored by the Space and Geophysics Laboratory of Applied Research Laboratories, The University of Texas at Austin. The GPSTk provides processing and analysis tools for GPS data. Clock Tools, a recent addition to the GPSTk, allows for basic clock stability analyses. These Clock Tools are interoperable with other GPSTk programs, allowing clock analyses to be easily run alongside other GPS analyses. The Clock Tools suite currently computes the Allan, overlapping Allan, modified Allan, total Allan, overlapping Hadamard, and dynamic Allan deviation stability metrics. These Clock Tools may be run from the command line with their output piped to other GPSTk programs. Data formatting and outlier removal routines for GPS and time interval analyzer datasets facilitate compatibility with the Clock Tools stability programs. Python and Octave graphing scripts were created to plot the raw data output by Clock Tools and current work is focused on a Qt-based graphical front-end for the suite. The graphical front-end will enable integrated stability metric selection and graphing. In the near term, we plan to expand the functionality of the graphical front-end and add noise-type identification functions. Results from the validation of Clock Tools are presented along with demonstrations of typical applications. Specifically, Clock Tools stability plots will be compared to those generated by Stable32. Analyses of RINEX datasets will be traced through the GPSTk toolchain, from calculation of observed range deviation to outlier removal, data parsing, stability calculation, and plot generation. A preview of the graphical front-end and its use will be presented. The analyses will be in the context of a worldwide GPS monitor station network with high-quality atomic frequency standards., See also ADM002186. Presented at the Annual Precise Time and Time Interval (PTTI) Systems and Applications Meeting (40th) held in Reston, Virginia on 1-4 December 2008. Published in the Proceedings of the Annual Precise Time and Time Interval (PTTI) Systems and Applications Meeting (40th), p255-274, 2008. The original document contains color images.

Studying the social and cultural transmission of behavior among animals helps to identify patterns and content of interaction. Killer whales likely acquire traits culturally based on their stable social groups, population-specific feeding behaviors, and group-distinctive vocal repertoires. Digital tags were used to record the movements and vocalizations of Norwegian killer whales. These animals carousel feed, corralling herring into a ball before tail slapping, incapacitating and eating the fish. Periods of tail slapping were characterized by elevated movement variability, heightened vocal activity, and call types containing orientation cues. Two types of behavioral sequence preceded the tight circling of carousel feeding. First, the animals swam directionally and in 2 of 3 instances were silent, suggesting that they may have located other foraging groups by eavesdropping. Second, tagged animals made broad horizontal loops as they dove in a manner consistent with corralling. All 4 of these occasions were accompanied by vocal activity, indicating that this and tail slapping may benefit from social communication. Killer whale vocalizations traditionally have been classified into discrete call types. Using human speech processing techniques, the author considered that calls alternatively consist of shared segments that can be recombined to form the stereotyped and variable repertoire. In a classification experiment, the characterization of calls using the whole call, a set of unshared segments, or a set of shared segments yielded equivalent performance. The shared segments required less information to parse the same vocalizations, suggesting a more parsimonious system of representation. This closer examination of the movements and vocalizations of Norwegian killer whales, combined with future work on ontogeny and transmission, will inform our understanding of whether and how culture plays a role in achieving population-specific behaviors in this species., Prepared in cooperation with the Woods Hole Oceanographic Institution, Woods Hole, MA.

The traditional natural language processing (NLP) pipeline incorporates multiple stages of linguistic analysis. Although errors are typically compounded through the pipeline, it is possible to reduce the errors in one stage by harnessing the results of the other stages. This thesis presents a new framework based on component interactions to approach this goal. The new framework applies all stages in a suitable order, with each stage generating multiple hypotheses and propagating them through the whole pipeline. The feedback from subsequent stages is then used to enhance the target stage by re-ranking these hypotheses and producing the best analysis. The effectiveness of this framework has been demonstrated by substantially improving the performance of Chinese and English entity extraction and Chinese-to-English entity translation. The inference knowledge includes monolingual interactions among information extraction stages such as name tagging, coreference resolution, relation extraction, and event extraction, as well as cross-lingual interaction between information extraction and machine translation. Such symbiosis of analysis components allows the author to incorporate information from a much wider context, spanning the entire document and even going across documents, and to utilize deeper semantic analysis. It will therefore be essential for the creation of a high-performance NLP pipeline.

For languages with inflectional morphology, development of a morphological parser is often a bottleneck for further development of computational linguistic capabilities. We focus on two difficulties: first, finding people with expertise in both computer programming and the linguistics of a particular language, and second, the short lifetime of software such as parsers. We then describe a methodology we have developed to split the task of building a parser for a language into two tasks, descriptive grammar development and formal grammar development. The two grammars are combined into a single document using Literate Programming. The formal grammar is designed not to be dependent on a particular parsing engine’s programming language, so that it can be readily ported to a new parsing engine, thus helping solve the software lifetime problem.

We describe a two-layer architecture for supporting semantic interpretation and domain reasoning in dialogue systems. Building systems that support both semantic interpretation and domain reasoning in a transparent and well-integrated manner is an unresolved problem because of the diverging requirements of the semantic representations used in contextual interpretation versus the knowledge representations used in domain reasoning. We propose an architecture that provides both portability and efficiency in natural language interpretation by maintaining separate semantic and domain knowledge representations, and integrating them via an ontology mapping procedure. The ontology mapping is used to obtain representations of utterances in a form most suitable for domain reasoners, and to automatically specialize the lexicon. The use of a linguistically motivated parser for producing semantic representations for complex natural language sentences facilitates building portable semantic interpretation components as well as connections with domain reasoners. Two evaluations demonstrate the effectiveness of our approach: we show that a small number of mapping rules is sufficient for customizing the generic semantic representation to a new domain, and that our automatic lexicon specialization technique improves parser speed and accuracy., Prepared in cooperation with the University of Edinburgh, UK. Sponsored in part by the Defense Advanced Research Projects Agency (DARPA).

Automatic detection of sentences in speech is useful to enrich speech recognition output and ease subsequent language processing modules. In the recent NIST evaluations for this task, an error rate was used to evaluate system performance. A variety of metrics such as F-measure, ROC or DET curves have also been explored in other studies. This paper aims to take a closer look at the evaluation issue for sentence boundary detection. We employ different metrics NIST error rate, classification error rate per word boundary, precision and recall, ROC curve, DET curve, precision-recall curve, and the area under the curves, to compare different system output. In addition we use two different corpora in order to evaluate the impact of different imbalance in the data set. We show that it is helpful to use curves as well as a single performance metric, and that different curves show different advantages in visualization. Furthermore, the data skewness also has an impact on the metrics., Prepared in cooperation with University of Texas, Austin, TX; and International Computer Science Institute, Berkeley, CA.

Information models are a critical tool that enables intelligence customers to quickly and accurately comprehend U.S. intelligence agency products. The Knowledge Pre-positioning System (KPS) is the standard repository for information models at the National Air and Space Intelligence Center (NASIC). The current approach used by NASIC to build a KPS information model is laborious and costly. Intelligence analysts design an information model using a manual, butcher-paper-based process. The output of their work is then entered into KPS by either a single NASIC KPS "database modeler" or a contractor (at a cost of roughly $100K to the organization). This thesis proposes a tool-supported approach that allows intelligence analysts to create information models for NASIC with almost no database modeler or contractor support. The approach allows analysts to express an information model as a concept map, a analyst-understandable model of an intelligence domain. An existing tool, CmapTools, supports the analyst-in-the-loop process of concept map creation. A completed concept map is automatically converted into KPS by a prototype tool called Cmap Conversion for KPS, which was created as part of this work. They restrict, to a reasonable degree, how analysts express concept maps within CmapTools to ensure that automatic conversion is possible. The authors validated their approach using a representative NASIC-provided KPS information model: performance of fixed-wing aircraft. Using these tools, a new information model was constructed in 4 hours and 20 minutes, a 89% improvement over the 40 hours estimated by NASIC to complete the same task using their existing approach. For this representative information model, NASIC estimates this approach would save them roughly $200K., The original document contains color images.

The U S. Army Research Laboratory's Battlespace Decision Support Team is exploring methods of portraying control or power influence in the battlespace. The Battlespace Terrain Ownership project uses resultant data from the successive application of three computer programs to present a graphical display of areas of influence in the battlespace: combat simulation, the data translation process, and the control algorithm and associated display. The first step involves the creation of a combat scenario in One Semi-Automated Forces (OneSAF) Testbed Baseline (OTB) v2.0; OTB provides data on all entities in the battlespace and both direct- and indirect-fire events. The second step is converting this data into a format for the control algorithm. The control algorithm then interprets different factors in the battlespace and provides a visual display. This report addresses the second step, the data translation process., The original document contains color images.

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.