SEARCH · Engineering Papers
Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.
Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.
This paper describes a tool for intersecting context-free grammars. Since this problem is undecidable the tool follows a refinement-based approach and implements a novel refinement which is complete for regularly separable grammars. We show its effectiveness for safety verification of recursive multi-threaded programs.
If G is a grammar such that in each noncontext-free rule of G, the right side contains a string of terminals longer than any terminal string appearing between two nonterminals in the left side; then the language generated by G is context-free. Six previous results follow as simple corollaries of this theorem.
If G is a grammar such that in each non-context-free rule of G, the right side contains a string of terminals longer than any terminal string appearing between two nonterminals in the left side, then the language generated by G is context free. Six previous results follow as corollaries of this theorem.
Equivalence of one-way grammars to context-free grammars, showing nonnecessity for restrictions on rules
Context-free language generation using nontrivial constraints on context-sensitive grammar rules
We analyze data from simulated aircraft encounters to validate and inform the development of a prototype aircraft collision avoidance system. The high-dimensional and heterogeneous time series dataset is analyzed to discover properties of near mid-air collisions (NMACs) and categorize the NMAC encounters. Domain experts use these properties to better organize and understand NMAC occurrences. Existing solutions either are not capable of handling high-dimensional and heterogeneous time series datasets or do not provide explanations that are interpretable by a domain expert. The latter is critical to the acceptance and deployment of safety-critical systems. To address this gap, we propose grammar-based decision trees along with a learning algorithm. Our approach extends decision trees with a grammar framework for classifying heterogeneous time series data. A context-free grammar is used to derive decision expressions that are interpretable, application-specific, and support heterogeneous data types. In addition to classification, we show how grammar-based decision trees can also be used for categorization, which is a combination of clustering and generating interpretable explanations for each cluster. We apply grammar-based decision trees to a simulated aircraft encounter dataset and evaluate the performance of four variants of our learning algorithm. The best algorithm is used to analyze and categorize near mid-air collisions in the aircraft encounter dataset. We describe each discovered category in detail and discuss its relevance to aircraft collision avoidance.
The research results described here are intended to enhance the effectiveness of the DATALINK interface that is scheduled by the Federal Aviation Administration (FAA) to be deployed during the 1990's to improve the safety of various aspects of aviation. While voice has a natural appeal as the preferred means of communication both among humans themselves and between humans and machines as the form of communication that people find most convenient, the complexity and flexibility of natural language are problematic, because of the confusions and misunderstandings that can arise as a result of ambiguity, unclear reference, intonation peculiarities, implicit inference, and presupposition. The DATALINK interface will avoid many of these problems by replacing voice with vision and speech with written instructions. This report describes results achieved to date on an on-going research effort to refine the protocol of the DATALINK system so as to avoid many of the linguistic problems that still remain in the visual mode. In particular, a working prototype DATALINK simulator system has been developed consisting of an unambiguous, context-free grammar and parser, based on the current air-traffic-control language and incorporated into a visual display involving simulated touch-screen buttons and three levels of menu screens. The system is written in the C programming language and runs on the Macintosh II computer. After reviewing work already done on the project, new tasks for further development are described.
In this paper, we describe a new discrete recurrent model with discrete external stacks for learning context-free grammars (or pushdown automata).
This position paper describes an approach to building spoken dialogue systems for environments containing multiple human speakers and hearers, and multiple robotic speakers and hearers. We address the issue, for robotic hearers, of whether the speech they hear is intended for them, or more likely to be intended for some other hearer. We will describe data collected during a series of experiments involving teams of multiple human and robots (and other software participants), and some preliminary results for distinguishing robot-directed speech from human-directed speech. The domain of these experiments is Mars-analogue planetary exploration. These Mars-analogue field studies involve two subjects in simulated planetary space suits doing geological exploration with the help of 1-2 robots, supporting software agents, a habitat communicator and links to a remote science team. The two subjects are performing a task (geological exploration) which requires them to speak with each other while also speaking with their assistants. The technique used here is to use a probabilistic context-free grammar language model in the speech recognizer that is trained on prior robot-directed speech. Intuitively, the recognizer will give higher confidence to an utterance if it is similar to utterances that have been directed to the robot in the past.
Recurrent neural networks have recently been shown to have the ability to learn regular and context-free grammars from examples. We show that while conventional analog recurrent networks try to form clusters in activation space to represent discrete states of the grammars during learning, and can be successful in doing so, the clusters so formed tend to become unstable as longer and longer test input strings are presented to the network.
Investigation of the conditions whereunder context-sensitive grammars generate context-free languages. The obtained results indicate that, if every noncontext-free rewriting rule of a context-sensitive grammar has as left context a string of terminal symbols and the left context is at least as long as the right context, then the language generated is context-free. Likewise, if every noncontext-free rewriting rule of a context-sensitive grammar has strings of terminal symbols as left and right contexts, then the language generated is also context-free.
Straightforward algorithm for converting context free grammars into pushdown-store automata
Consideration of the problem of explaining the use of context in generating noncontext-free languages. A number of existing results regarding the constraints placed on the form of the rules (i.e., on the context) of context-sensitive grammars are reviewed and interpreted. Three types of constraints are considered - namely, constraints which do not restrict the weak generative capacity of the class of grammars (i.e., all the context-sensitive languages are generated by grammars with these constraints), constraints which restrict the weak generative capacity to the extent that all context-sensitive languages are not generated but some noncontext-free languages are generated, and constraints which restrict the weak generative capacity to such an extent that only context-free languages are generated.