SEARCH · Search NASA

Results for “Formal Reasoning”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 127 records · Page 7

All sources NASA NTRS DOE OSTI

NASA NTRS1992

Reformulating Non-Monotonic Theories for Inference and Updating

We aim to help build programs that do large-scale, expressive non-monotonic reasoning (NMR): especially, 'learning agents' that store, and revise, a body of conclusions while continually acquiring new, possibly defeasible, premise beliefs. Currently available procedures for forward inference and belief revision are exhaustive, and thus impractical: they compute the entire non-monotonic theory, then re-compute from scratch upon updating with new axioms. These methods are thus badly intractable. In most theories of interest, even backward reasoning is combinatoric (at least NP-hard). Here, we give theoretical results for prioritized circumscription that show how to reformulate default theories so as to make forward inference be selective, as well as concurrent; and to restrict belief revision to a part of the theory. We elaborate a detailed divide-and-conquer strategy. We develop concepts of structure in NM theories, by showing how to reformulate them in a particular fashion: to be conjunctively decomposed into a collection of smaller 'part' theories. We identify two well-behaved special cases that are easily recognized in terms of syntactic properties: disjoint appearances of predicates, and disjoint appearances of individuals (terms). As part of this, we also definitionally reformulate the global axioms, one by one, in addition to applying decomposition. We identify a broad class of prioritized default theories, generalizing default inheritance, for which our results especially bear fruit. For this asocially monadic class, decomposition permits reasoning to be localized to individuals (ground terms), and reduced to propositional. Our reformulation methods are implementable in polynomial time, and apply to several other NM formalisms beyond circumscription.

Grosof, Benjamin N.↗

NASA NTRS2000

Analysis of Phase-Type Stochastic Petri Nets With Discrete and Continuous Timing

The Petri net formalism is useful in studying many discrete-state, discrete-event systems exhibiting concurrency, synchronization, and other complex behavior. As a bipartite graph, the net can conveniently capture salient aspects of the system. As a mathematical tool, the net can specify an analyzable state space. Indeed, one can reason about certain qualitative properties (from state occupancies) and how they arise (the sequence of events leading there). By introducing deterministic or random delays, the model is forced to sojourn in states some amount of time, giving rise to an underlying stochastic process, one that can be specified in a compact way and capable of providing quantitative, probabilistic measures. We formalize a new non-Markovian extension to the Petri net that captures both discrete and continuous timing in the same model. The approach affords efficient, stationary analysis in most cases and efficient transient analysis under certain restrictions. Moreover, this new formalism has the added benefit in modeling fidelity stemming from the simultaneous capture of discrete- and continuous-time events (as opposed to capturing only one and approximating the other). We show how the underlying stochastic process, which is non-Markovian, can be resolved into simpler Markovian problems that enjoy efficient solutions. Solution algorithms are provided that can be easily programmed.

Jones, Robert L.↗

NASA NTRS1995

Introduction to Penelope

A formal program verification is a (mathematical) proof that a program executed according to its intended model meets some specification. This proves that the algorithm defined by the program is correct in the precise technical sense of being consistent with a particular specification. A program correct in this sense is free from a large and important class of errors, even though its behavior may still produce unintended results--either because the implementation of the programming language itself does not match the model of execution, or because the specification does not correctly express the user's intentions. Penelope is a prototype system for interactively developing and verifying programs that are written in a rich subset of sequential Ada. Penelope can be used to develop a program and its correctness proof incrementally, and in concert with one another. Incrementality is used in a number of ways to help make verification more tractable and more productive. For example, if an already-verified program is modified, one can attempt to prove the modified version by replaying and modifying the original verification. Penelope's specification language, Larch/Ada, belongs to the family of Larch interface languages. Larch/Ada scales up properly, in the sense that it is demonstrably sound to decompose a system hierarchically and reason locally about the implementation of each piece. Penelope has been applied in various demonstration projects--for specification (guidance control, distributed operating systems), verification (of off-the-shelf code), and formal development (by non-expert as well as expert users). Some features of Penelope have been embodied in Ada Wise, a lint-like non-interactive tool that warns of the potential for certain dynamic semantic errors in Ada programs.

Guaspari, David↗

NASA NTRS2021

Defining and Reasoning about Model-based Safety Analysis: A Review

Model-based safety analysis (MBSA) has been around for over two decades. The benefits of MBSA have been well-documented in the literature, such as tackling complexity, introducing Formal Methods to eliminate the ambiguity in the traditional safety analysis, using automation to replace the error-prone manual safety modeling process, and ensuring consistency between the design model and the safety model. However, there is still a lack of consensus on what MBSA even is. This paper provides an approach towards developing such a consensus

model-based↗

NASA NTRS1985

A knowledge based software engineering environment testbed

The Carnegie Group Incorporated and Boeing Computer Services Company are developing a testbed which will provide a framework for integrating conventional software engineering tools with Artifical Intelligence (AI) tools to promote automation and productivity. The emphasis is on the transfer of AI technology to the software development process. Experiments relate to AI issues such as scaling up, inference, and knowledge representation. In its first year, the project has created a model of software development by representing software activities; developed a module representation formalism to specify the behavior and structure of software objects; integrated the model with the formalism to identify shared representation and inheritance mechanisms; demonstrated object programming by writing procedures and applying them to software objects; used data-directed and goal-directed reasoning to, respectively, infer the cause of bugs and evaluate the appropriateness of a configuration; and demonstrated knowledge-based graphics. Future plans include introduction of knowledge-based systems for rapid prototyping or rescheduling; natural language interfaces; blackboard architecture; and distributed processing

Gill, C.↗

NASA NTRS2001

A New Sputnik Surprise?

This paper suggests that a new "Sputnik surprise" in the form of a joint Chinese-Russian lunar base program may emerge in this decade. The Moon as a whole has been shown to be territory of strategic value, with discovery of large amounts of hydrogen (probably water ice) at the lunar poles and helium 3 everywhere in the soil, in addition to the Moon's scientific value as an object of study and as a platform for astronomy. There is thus good reason for a return to the Moon, robotically or manned. Relations between China and Russia have thawed since the mid-1990s, and the two countries have a formal space cooperation pact. It is argued here that a manned lunar program would be feasible within 5 years, using modern technology and proven spacecraft and launch vehicles. The combination of Russian lunar hardware with Chinese space technology would permit the two countries together to take the lead in solar system exploration in the 21st century.

Lowman, Paul D., Jr.↗

NASA NTRS2014

Formation of Nucleobases from the UV Irradiation of Pyrimidine in Astrophysical Ice Analogs

Nucleobases are the informational subunits of DNA and RNA. They consist of Nheterocycles that belong to either the pyrimidine-base group (uracil, cytosine, and thymine) or the purinebase group (adenine and guanine). Several nucleobases, mostly purine bases, have been detected in meteorites [1-3], with isotopic signatures consistent with an extraterrestrial origin [4]. Uracil is the only pyrimidine-base compound formally reported in meteorites [2], though the presence of cytosine cannot be ruled out [5,6]. However, the actual process by which the uracil was made and the reasons for the non-detection of thymine in meteorites have yet to be fully explained. Although no N-heterocycles have ever been observed in the ISM [7,8], the positions of the 6.2-μm interstellar emission features suggest a population of such molecules is likely to be present [9]. In this work we study the formation of pyrimidine-based molecules, including the three nucleobases uracil, cytosine, and thymine from the ultraviolet (UV) irradiation of pyrimidine in ices consisting of several combinations of H(sub2)O, NH(sub3), CH(sub3)OH, and CH(sub4) at low temperature, in order to simulate the astrophysical conditions under which prebiotic species may be formed in the interstellar medium, in the protosolar nebula, and on icy bodies of the Solar System.

UV Irradiation↗

NASA NTRS1996

A Model-based Approach to Reactive Self-Configuring Systems

This paper describes Livingstone, an implemented kernel for a self-reconfiguring autonomous system, that is reactive and uses component-based declarative models. The paper presents a formal characterization of the representation formalism used in Livingstone, and reports on our experience with the implementation in a variety of domains. Livingstone's representation formalism achieves broad coverage of hybrid software/hardware systems by coupling the concurrent transition system models underlying concurrent reactive languages with the discrete qualitative representations developed in model-based reasoning. We achieve a reactive system that performs significant deductions in the sense/response loop by drawing on our past experience at building fast prepositional conflict-based algorithms for model-based diagnosis, and by framing a model-based configuration manager as a prepositional, conflict-based feedback controller that generates focused, optimal responses. Livingstone automates all these tasks using a single model and a single core deductive engine, thus making significant progress towards achieving a central goal of model-based reasoning. Livingstone, together with the HSTS planning and scheduling engine and the RAPS executive, has been selected as the core autonomy architecture for Deep Space One, the first spacecraft for NASA's New Millennium program.

Williams, Brian C.↗

NASA NTRS2002

Technical Challenges of Drilling on Mars

In the last year, NASA's Mars science advisory committee (MEPAG: Mars Exploration Payload Advisory Group) has formally recommended that deep drilling be undertaken as a priority investigation to meet astrobiology and geology goals. This proposed new dimension in Mars exploration has come about for several reasons. Firstly, geophysical models of the martian subsurface environment indicate that we may well find liquid water (in the form of brines) under ground-ice at depths of several kilometers near the equator. On Earth we invariably find life forms associated with any environmental niche that supports liquid water. New data from the Mars Global Surveyor have shown that the most recent volcanism on Mars is very young so we cannot rule out contemporary volcanism -- in which case subsurface temperatures consistent with having water in its liquid phase may be found at relatively shallow depths. Secondly, in recent decades we have learned to our surprise that the Earth's subsurface (microbial) biosphere extends to depths of many kilometers and this discovery provides the basis for planning to explore the martian subsurface in search of ancient or even extant microbial life forms. We know (from Viking measurements) that all the biogenic elements (C, H, O, N, P, S) are available on Mars. What we therefore hope to learn is whether or not the evolution of life is inevitable given the necessary ingredients and, by implication, whether the Universe may be teeming with life. The feasibility of drilling deep into the surface of Mars has been the subject of increasing attention within NASA (and more recently among some of its international partners) for several years and this led to a broad-based feasibility study carried out by the Los Alamos National Laboratory and, subsequently, to the development of several hardware prototypes. This paper is intended to provide a general survey of that activity.

Briggs, Geoffrey↗

NASA NTRS1992

Software design as a problem in learning theory (a research overview)

Our interest in automating software design has come out of our research in automated reasoning, inductive inference, learnability, and algebraic machine theory. We have investigated these areas extensively, in connection with specific problems of language representation, acquisition, processing, and design. In the case of formal context-free (CF) languages we established existence of finite learnable models ('behavioral realizations') and procedures for constructing them effectively. We also determined techniques for automatic construction of the models, inductively inferring them from finite examples of how they should 'behave'. These results were obtainable due to appropriate representation of domain knowledge, and constraints on the domain that the representation defined. It was when we sought to generalize our results, and adapt or apply them, that we began investigating the possibility of determining similar procedures for constructing correct software. Discussions with other researchers led us to examine testing and verification processes, as they are related to inference, and due to their considerable importance in correct software design. Motivating papers by other researchers, led us to examine these processes in some depth. Here we present our approach to those software design issues raised by other researchers, within our own theoretical context. We describe our results, relative to those of the other researchers, and conclude that they do not compare unfavorably.

Fass, Leona F.↗

NASA NTRS2009

Deriving Safety Cases from Automatically Constructed Proofs

Formal proofs provide detailed justification for the validity of claims and are widely used in formal software development methods. However, they are often complex and difficult to understand, because the formalism in which they are constructed and encoded is usually machine-oriented, and they may also be based on assumptions that are not justified. This causes concerns about the trustworthiness of using formal proofs as arguments in safety-critical applications. Here, we present an approach to develop safety cases that correspond to formal proofs found by automated theorem provers and reveal the underlying argumentation structure and top-level assumptions. We concentrate on natural deduction style proofs, which are closer to human reasoning than resolution proofs, and show how to construct the safety cases by covering the natural deduction proof tree with corresponding safety case fragments. We also abstract away logical book-keeping steps, which reduces the size of the constructed safety cases. We show how the approach can be applied to the proofs found by the Muscadet prover.

Basir, Nurlida↗

NASA NTRS2014

State Event Models for the Formal Analysis of Human-Machine Interactions

The work described in this paper was motivated by our experience with applying a framework for formal analysis of human-machine interactions (HMI) to a realistic model of an autopilot. The framework is built around a formally defined conformance relation called "fullcontrol" between an actual system and the mental model according to which the system is operated. Systems are well-designed if they can be described by relatively simple, full-control, mental models for their human operators. For this reason, our framework supports automated generation of minimal full-control mental models for HMI systems, where both the system and the mental models are described as labelled transition systems (LTS). The autopilot that we analysed has been developed in the NASA Ames HMI prototyping tool ADEPT. In this paper, we describe how we extended the models that our HMI analysis framework handles to allow adequate representation of ADEPT models. We then provide a property-preserving reduction from these extended models to LTSs, to enable application of our LTS-based formal analysis algorithms. Finally, we briefly discuss the analyses we were able to perform on the autopilot model with our extended framework.

State-event Models↗

NASA NTRS2023

Performance of the IVS R1 and R4 Sessions

The International VLBI Service for Geodesy and Astrometry (IVS) has observed the weekly IVS-R1 (R1) and IVS-R4 (R4) series of sessions since 2002. These regular series are generally stable in the sense that the networks were designed to be similar from week to week. The uniformity of these series has allowed researchers to conduct many scientific investigations. The IVS also observes with other networks that allow continued sampling of data from all VLBI stations, but the R1 and R4 observing sessions are a dominant part of overall VLBI observing accounting for 1841 sessions out of a total of 3129 24-hour sessions from 2002.0 to 2020.0 (where the last R1 and R4 in 2019 was on December 30 and December 26, respectively). In this paper, we investigate the evolution of these series in terms of their observing networks. We also discuss the construction of the R1 and R4 networks and the scheduling of these sessions. The performance of these networks in terms of the formal precision of polar motion have improved by factors of 2–3 over the period from 2002.0 to 2018.0. UT1 precision improved by a factor of about 1.2–1.5. The main reason for this improvement is the increased size of the networks. We also discuss the effect on this improvement arising from changes in the data rate and the number of observed sources. There is some degradation in performance after 2018 that is most likely due to a decline in the number of available network stations.

Cynthia C. Thomas↗

NASA NTRS2022

Line Coupling and Line Mixing Effects on Calculated Widths of Symmetric-Top Molecules With the k-Degeneracy: A Theoretical Study of N 2 -, O 2 -, and Air-Broadened Lines of CH 3 I

Calculations of the N 2 -, O 2 - and air-broadened widths, together with their temperature dependence exponents have been made for transitions of CH 3 I in the v 5 and v 6 bands. The calculations are based on a semi-classical line shape formalism developed by the current authors through modifying and refining the Robert-Bonamy formalism. In recent years, we have applied this formalism for linear molecules, symmetric-top molecules with inversion symmetry, and asymmetric-top molecules. For symmetric-top molecules with the k degeneracy such as CH 3 I, the formalism has a new feature. In this case, one should consider each of the CH 3 I transitions labeled by k i or ƒ ≠ 0 as a doublet. Then, one needs to consider the effects of the line mixing process between these two components. Comparisons of our theoretical predictions with some data available demonstrate a very reasonable agreement. Finally we propose new experiments at higher perturber pressures that would enable one to check the theoretically calculated relaxation matrices and to extend the analysis to the interdoublet mixing effects.

Line coupling↗

DOE OSTI2025

Theorems in Service of Sound Composition, Rapid Modeling and Scalable Analysis

This project extends the state of the art in formal verification modeling with modules and automatically checkable data-sharing patterns such that component modules can retain their assurance case when composed within a larger system. For users, smaller models make reasoning easier and help to ensure they accurately reflect text specifications. For automated methods, smaller models give exponential benefits for verification algorithm execution time.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1989

Ginzburg-Landau theory for the solid-liquid interface of bcc elements. II - Application to the classical one-component plasma, the Wigner crystal, and He-4

The previously developed Ginzburg-Landau theory for calculating the crystal-melt interfacial tension of bcc elements to treat the classical one-component plasma (OCP), the charged fermion system, and the Bose crystal. For the OCP, a direct application of the theory of Shih et al. (1987) yields for the surface tension 0.0012(Z-squared e-squared/a-cubed), where Ze is the ionic charge and a is the radius of the ionic sphere. Bose crystal-melt interface is treated by a quantum extension of the classical density-functional theory, using the Feynman formalism to estimate the relevant correlation functions. The theory is applied to the metastable He-4 solid-superfluid interface at T = 0, with a resulting surface tension of 0.085 erg/sq cm, in reasonable agreement with the value extrapolated from the measured surface tension of the bcc solid in the range 1.46-1.76 K. These results suggest that the density-functional approach is a satisfactory mean-field theory for estimating the equilibrium properties of liquid-solid interfaces, given knowledge of the uniform phases.

Zeng, X. C.↗

NASA NTRS1997

Algorithms for Performance, Dependability, and Performability Evaluation using Stochastic Activity Networks

Modeling tools and technologies are important for aerospace development. At the University of Illinois, we have worked on advancing the state of the art in modeling by Markov reward models in two important areas: reducing the memory necessary to numerically solve systems represented as stochastic activity networks and other stochastic Petri net extensions while still obtaining solutions in a reasonable amount of time, and finding numerically stable and memory-efficient methods to solve for the reward accumulated during a finite mission time. A long standing problem when modeling with high level formalisms such as stochastic activity networks is the so-called state space explosion, where the number of states increases exponentially with size of the high level model. Thus, the corresponding Markov model becomes prohibitively large and solution is constrained by the the size of primary memory. To reduce the memory necessary to numerically solve complex systems, we propose new methods that can tolerate such large state spaces that do not require any special structure in the model (as many other techniques do). First, we develop methods that generate row and columns of the state transition-rate-matrix on-the-fly, eliminating the need to explicitly store the matrix at all. Next, we introduce a new iterative solution method, called modified adaptive Gauss-Seidel, that exhibits locality in its use of data from the state transition-rate-matrix, permitting us to cache portions of the matrix and hence reduce the solution time. Finally, we develop a new memory and computationally efficient technique for Gauss-Seidel based solvers that avoids the need for generating rows of A in order to solve Ax = b. This is a significant performance improvement for on-the-fly methods as well as other recent solution techniques based on Kronecker operators. Taken together, these new results show that one can solve very large models without any special structure.

Deavours, Daniel D.↗

NASA NTRS2019

Overview of the PLEXIL Plan Execution Technology and its Applications in Autonomous Piloting Projects at NASA

Automated planning is a key Artificial Intelligence technology enabling Unmanned Aerial Systems (UAS) and the eminent reality of Urban Air Mobility (UAM). It produces plans, which formalize procedures often performed by humans. Plans differ from other kinds of computer programs in their ability to react and interact with a dynamically changing environment. Aviation plans must encode the procedural knowledge, reasoning capability, and capacity for multi-tasking held by competent human pilots. Correct execution of these plans (performed by software called an executive) in the dynamic airspace environment is vital to the success of each automated flight, and the safety of the vehicle and all things in its path. In the early 2000s NASA developed a plan representation language and executive called PLEXIL (Plan Execution Interchange Language) that has successfully been applied in several NASA aviation and UAS projects. Autonomy Operating System (AOS), Cockpit Hierarchical Automated Planning and Execution (CHAP-E), and ICAROUS are all projects that have used PLEXIL to help encode and automatically execute flight procedures, some normally performed by human pilots. AOS also automates a subset of pilot/Air Traffic Control communication towards enabling UAS entry into the National Airspace. PLEXIL has been open-source software since 2008 and has seen usage in a wide range of prototypical autonomy applications in academia, government, and industry. In this presentation, we describe PLEXIL and highlight its significant accomplishments in the aviation domain.

Dalal, Michael↗