Digital Proving Ground: VIPER Rover Simulator (RSIM)
Explore the source record for details and available documents.
lunar rover↗
SEARCH · Search NASA
Results for “Proving”
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.
Prove-It: A Proof Assistant for Organizing and Verifying General Mathematical Knowledge.
Abstract not provided.
Witzel, Wayne↗
Proof-Carrying Code with Correct Compilers
In the late 1990s, proof-carrying code was able to produce machine-checkable safety proofs for machine-language programs even though (1) it was impractical to prove correctness properties of source programs and (2) it was impractical to prove correctness of compilers. But now it is practical to prove some correctness properties of source programs, and it is practical to prove correctness of optimizing compilers. We can produce more expressive proof-carrying code, that can guarantee correctness properties for machine code and not just safety. We will construct program logics for source languages, prove them sound w.r.t. the operational semantics of the input language for a proved-correct compiler, and then use these logics as a basis for proving the soundness of static analyses.
Appel, Andrew W.↗
An Integrated Environment for Efficient Formal Design and Verification
The general goal of this project was to improve the practicality of formal methods by combining techniques from model checking and theorem proving. At the time the project was proposed, the model checking and theorem proving communities were applying different tools to similar problems, but there was not much cross-fertilization. This project involved a group from SRI that had substantial experience in the development and application of theorem-proving technology, and a group at Stanford that specialized in model checking techniques. Now, over five years after the proposal was submitted, there are many research groups working on combining theorem-proving and model checking techniques, and much more communication between the model checking and theorem proving research communities. This project contributed significantly to this research trend. The research work under this project covered a variety of topics: new theory and algorithms; prototype tools; verification methodology; and applications to problems in particular domains.
Source record↗
Regression Verification Using Impact Summaries
Regression verification techniques are used to prove equivalence of syntactically similar programs. Checking equivalence of large programs, however, can be computationally expensive. Existing regression verification techniques rely on abstraction and decomposition techniques to reduce the computational effort of checking equivalence of the entire program. These techniques are sound but not complete. In this work, we propose a novel approach to improve scalability of regression verification by classifying the program behaviors generated during symbolic execution as either impacted or unimpacted. Our technique uses a combination of static analysis and symbolic execution to generate summaries of impacted program behaviors. The impact summaries are then checked for equivalence using an o-the-shelf decision procedure. We prove that our approach is both sound and complete for sequential programs, with respect to the depth bound of symbolic execution. Our evaluation on a set of sequential C artifacts shows that reducing the size of the summaries can help reduce the cost of software equivalence checking. Various reduction, abstraction, and compositional techniques have been developed to help scale software verification techniques to industrial-sized systems. Although such techniques have greatly increased the size and complexity of systems that can be checked, analysis of large software systems remains costly. Regression analysis techniques, e.g., regression testing [16], regression model checking [22], and regression verification [19], restrict the scope of the analysis by leveraging the differences between program versions. These techniques are based on the idea that if code is checked early in development, then subsequent versions can be checked against a prior (checked) version, leveraging the results of the previous analysis to reduce analysis cost of the current version. Regression verification addresses the problem of proving equivalence of closely related program versions [19]. These techniques compare two programs with a large degree of syntactic similarity to prove that portions of one program version are equivalent to the other. Regression verification can be used for guaranteeing backward compatibility, and for showing behavioral equivalence in programs with syntactic differences, e.g., when a program is refactored to improve its performance, maintainability, or readability. Existing regression verification techniques leverage similarities between program versions by using abstraction and decomposition techniques to improve scalability of the analysis [10, 12, 19]. The abstractions and decomposition in the these techniques, e.g., summaries of unchanged code [12] or semantically equivalent methods [19], compute an over-approximation of the program behaviors. The equivalence checking results of these techniques are sound but not complete-they may characterize programs as not functionally equivalent when, in fact, they are equivalent. In this work we describe a novel approach that leverages the impact of the differences between two programs for scaling regression verification. We partition program behaviors of each version into (a) behaviors impacted by the changes and (b) behaviors not impacted (unimpacted) by the changes. Only the impacted program behaviors are used during equivalence checking. We then prove that checking equivalence of the impacted program behaviors is equivalent to checking equivalence of all program behaviors for a given depth bound. In this work we use symbolic execution to generate the program behaviors and leverage control- and data-dependence information to facilitate the partitioning of program behaviors. The impacted program behaviors are termed as impact summaries. The dependence analyses that facilitate the generation of the impact summaries, we believe, could be used in conjunction with other abstraction and decomposition based approaches, [10, 12], as a complementary reduction technique. An evaluation of our regression verification technique shows that our approach is capable of leveraging similarities between program versions to reduce the size of the queries and the time required to check for logical equivalence. The main contributions of this work are: - A regression verification technique to generate impact summaries that can be checked for functional equivalence using an off-the-shelf decision procedure. - A proof that our approach is sound and complete with respect to the depth bound of symbolic execution. - An implementation of our technique using the LLVMcompiler infrastructure, the klee Symbolic Virtual Machine [4], and a variety of Satisfiability Modulo Theory (SMT) solvers, e.g., STP [7] and Z3 [6]. - An empirical evaluation on a set of C artifacts which shows that the use of impact summaries can reduce the cost of regression verification.
Backes, John↗
Applying the Euclidean-signature semi-classical method to the quantum Taub models with a cosmological constant and aligned electromagnetic field
We prove the existence of a countably infinite number of “excited” states for the Lorentzian-signature Taub–Wheeler–DeWitt (WDW) equation when a cosmological constant is present using the Euclidean-signature semi-classical method. We also find a “ground” state solution when both an aligned electromagnetic field and cosmological constant are present; as a result, conjecture that the Euclidean-signature semi classical method can be used to prove the existence of a countably “infinite” number of “excited” states when the two aforementioned matter sources are present. Afterward, we prove the existence of asymptotic solutions to the vacuum Taub–WDW equation using the “no boundary” and “wormhole” solutions of the Taub Euclidean-signature Hamilton–Jacobi equation and compare their mathematical properties. We then discuss the fascinating qualitative properties of the wave functions we have computed. By utilizing the Euclidean-signature semi-classical method in the above manner, we further show its ability to prove the existence of solutions to Lorentzian-signature equations without having to invoke a Wick rotation. This feature of not needing to apply a Wick rotation makes this method potentially very useful for tackling a variety of problems in bosonic relativistic field theory and quantum gravity
71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
Designing Secure and Resilient Cyber-Physical Systems Using Formal Models
This work-in-progress paper proposes a design methodology that addresses the complexity and heterogeneity of cyber-physical systems (CPS) while simultaneously proving resilient control logic and security properties. The design methodology involves a formal methods-based approach by translating the complex control logic and security properties of a water flow CPS into timed automata. Timed automata are a formal model that describes system behaviors and properties using mathematics-based logic languages with precision. Due to the semantics that are used in developing the formal models, verification techniques, such as theorem proving and model checking, are used to mathematically prove the specifications and security properties of the CPS. This work-in-progress paper aims to highlight the need for formalizing plant models by creating a timed automata of the physical portions of the water flow CPS. Extending the time automata with control logic, network security, and privacy control processes is investigated. The final model will be formally verified to prove the design specifications of the water flow CPS to ensure efficacy and security.
42 ENGINEERING↗
Discreteness and integrality in Conformal Field Theory
Various observables in compact CFTs are required to obey positivity, discreteness, and integrality. Positivity forms the crux of the conformal bootstrap, but understanding of the abstract implications of discreteness and integrality for the space of CFTs is lacking. We systematically study these constraints in two-dimensional, non-holomorphic CFTs, making use of two main mathematical results. First, we prove a theorem constraining the behavior near the cusp of integral, vector-valued modular functions. Second, we explicitly construct non-factorizable, non-holomorphic cuspidal functions satisfying discreteness and integrality, and prove the non-existence of such functions once positivity is added. Application of these results yields several bootstrap-type bounds on OPE data of both rational and irrational CFTs, including some powerful bounds for theories with conformal manifolds, as well as insights into questions of spectral determinacy. We prove that in rational CFT, the spectrum of operator twists t ≥ c/12 is uniquely determined by its complement. Likewise, we argue that in generic CFTs, the spectrum of operator dimensions Δ > c–1/12 is uniquely determined by its complement, absent fine-tuning in a sense we articulate. Finally, we discuss implications for black hole physics and the (non-)uniqueness of a possible ensemble interpretation of AdS 3 gravity.
72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
Electron–phonon interaction in Kondo lattice systems
Highlights: • Rigorous study of ground state properties of the Kondo lattice model with an electron–phonon. • The ground state is proved to be unique. • The total spin of the ground state is determined according to the lattice structure. • Novel applications of order preserving operator inequalities. We study ground state properties of the Kondo lattice model with an electron–phonon interaction. The ground state is proved to be unique; in addition, the total spin of the ground state is determined according to the lattice structure. To prove the assertions, an extension of the method of spin reflection positivity is given in terms of order preserving operator inequalities.
71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
Projector-Based Quantum Embedding for Molecular Systems: An Investigation of Three Partitioning Approaches
Projector-based embedding is a relatively recent addition to the collection of methods that seek to utilize chemical locality to provide improved computational efficiency. This work considers the interactions between the different proposed procedures for this method and their effects on the accuracy of the results. The interplay between the embedded background, projector type, partitioning scheme, and level of atomic orbital (AO) truncation are investigated on a selection of reactions from the literature. The Huzinaga projection approach proves to be more reliable than the level-shift projection when paired with other procedural options. Active subsystem partitioning from the subsystem projected AO decomposition (SPADE) procedure proves slightly better than the combination of Pipek-Mezey localization and Mulliken population screening (PMM). Along with these two options, a new partitioning criteria is proposed based on subsystem von Neumann entropy and the related subsystem orbital occupancy. This new method overlaps with the previous PMM method, but the screening process is computationally simpler. Finally, AO truncation proves to be a robust option for the tested systems when paired with the Huzinaga projection, with satisfactory results being acquired at even the most severe truncation level.
37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
A solid electrolyte interphase to protect the sulfurized polyacrylonitrile (SPAN) composite for Li–S batteries: computational approach addressing the electrolyte/SPAN interfacial reactivity
This study addresses the reactivity of multiple solvents and lithium bis(fluorosulfonyl)imide (LiFSI) at the interface with sulfurized polyacrylonitrile (SPAN) in multiple stages of lithiation via ab initio molecular dynamics simulations. Here, both ether 1,3-dioxolane (DOL) and dimethyl carbonate (DMC) proved stable on the lithiated SPAN surface regardless of the lithium content, meaning that neither of these species likely contributes to growing a solid electrolyte interphase (SEI) coating to protect the SPAN composite. Conversely, cyclic carbonates, ethylene carbonate (EC) and fluoroethylene carbonate (FEC) are shown to be very active. The EC reduction occurs only on a highly lithiated surface with a 3.0 Li/S molar ratio, the equivalent of the SPAN composite in an over-discharge regime with voltages close to 0.0 V vs. Li/Li + . The FEC reduction starts with a 2.0 Li/S molar ratio and above, suggesting that FEC could act as a useful additive in electrolyte formulations with EC. Both EC and FEC follow multiple reduction mechanisms to produce complex reduction products and LiF in the FEC case. We provide a mechanistic description for each detected decomposition path. The LiFSI salt also proves reactive against the lithiated SPAN surface. The FSI – defluorination is the dominant reduction path. However, the SO 2 NSO 2 F – and SO 2 NSO 2 2– species proved stable against S–N cleavage. This behavior makes the LiFSI salt a potential candidate for SPAN-based Li–S batteries because it produces LiF without releasing SO 2 .
25 ENERGY STORAGE↗
Asymptotic reversibility of thermal operations for interacting quantum spin systems via generalized quantum Stein’s lemma
Abstract For quantum spin systems in any spatial dimension with a local, translation-invariant Hamiltonian, we prove that asymptotic state convertibility from a quantum state to another one by a thermodynamically feasible class of quantum dynamics, called thermal operations, is completely characterized by the Kullback–Leibler (KL) divergence rate, if the state is translation-invariant and spatially ergodic. Our proof consists of two parts and is phrased in terms of a branch of the quantum information theory called the resource theory. First, we prove that any states, for which the min and max Rényi divergences collapse approximately to a single value, can be approximately reversibly converted into one another by thermal operations with the aid of a small source of quantum coherence. Second, we prove that these divergences collapse asymptotically to the KL divergence rate for any translation-invariant ergodic state. We show this via a generalization of the quantum Stein’s lemma for quantum hypothesis testing beyond independent and identically distributed situations. Our result implies that the KL divergence rate serves as a thermodynamic potential that provides a complete characterization of thermodynamic convertibility of ergodic states of quantum many-body systems in the thermodynamic limit, including out-of-equilibrium and fully quantum situations.
Physics↗
Multi-pronged approach to improving carbon utilization by cyanobacterial cultures
The goal of this project was to increase the efficiency of carbon utilization by a Synechocystis biofuel production strain in a photobioreactor system by at least 50% using a multi-pronged approach that combined the best features of both biological and physicochemical CO 2 capture technologies to: 1) increase rates and extent of CO 2 absorption into the culture medium by addition of biocompatible amine solvents and a nanobubble gas delivery system, and 2) increase cellular rates of inorganic carbon uptake and carbon fixation through genetic engineering. In addition, the project plan included evaluating the use of fermentation effluent gases as a CO 2 source and demonstrating performance under outdoor conditions in closed-pond photobioreactor systems. These combined efforts would be guided by integrated technoeconomic and life-cycle analyses. Both physicochemical CO 2 capture technologies explored proved to be successful. The amine solvent monoethanolamine (MEA) was found to be biocompatible with a Synechocystis laurate production strain. Using an adaptive evolution strategy, an MEA-tolerant laurate production strain was developed that showed significantly increased carbon utilization over the parent strain. To our knowledge this was the first time nanobubble (NB) technology had been used as a carbon delivery system for algae production and it also proved quite successful as a proof of concept. Solutions containing CO 2 nanobubbles (Nano-BG11) at concentrations significantly higher than the aqueous CO 2 concentrations achieved with gas sparging were successfully generated and characterized with regard to bubble size (nm), concentration (NB/L), and pH stability as per project plan. Growth studies proved challenging. However, once the source of a puzzling growth defect was found and remedied Synechocystis was able to grow somewhat better in Nano-BG11 than in standard BG11 medium.
09 BIOMASS FUELS↗
Modeling the TetraSpar Floating Offshore Wind Turbine Foundation as a Flexible Structure in OrcaFlex and OpenFAST
Floating offshore wind turbine technology has seen an increasing and continuous development in recent years. When designing the floating platforms, both experimental and numerical tools are applied, with the latter often using time-domain solvers based on hydro-load estimation from a Morison approach or a boundary element method. Commercial software packages such as OrcaFlex, or open-source software such as OpenFAST, are often used where the floater is modeled as a rigid six degree-of-freedom body with loads applied at the center of gravity. However, for final structural design, it is necessary to have information on the distribution of loads over the entire body and to know local internal loads in each component. This paper uses the TetraSpar floating offshore wind turbine design as a case study to examine new modeling approaches in OrcaFlex and OpenFAST that provide this information. The study proves the possibility of applying the approach and the extraction of internal loads, while also presenting an initial code-to-code verification between OrcaFlex and OpenFAST. As can be expected, comparing the flexible model to a rigid-body model proves how motion and loads are affected by the flexibility of the structure. OrcaFlex and OpenFAST generally agree, but there are some differences in results due to different modeling approaches. Since no experimental data are available in the study, this paper only forms a baseline for future studies but still proves and describes the possibilities of the approach and codes.
17 WIND ENERGY↗
An extension of the Laplace transform to Schwartz distributions
A characterization of the Laplace transform is developed which extends the transform to the Schwartz distributions. The class of distributions includes the impulse functions and other singular functions which occur as solutions to ordinary and partial differential equations. The standard theorems on analyticity, uniqueness, and invertibility of the transform are proved by using the characterization as the definition of the Laplace transform. The definition uses sequences of linear transformations on the space of distributions which extends the Laplace transform to another class of generalized functions, the Mikusinski operators. It is shown that the sequential definition of the transform is equivalent to Schwartz' extension of the ordinary Laplace transform to distributions but, in contrast to Schwartz' definition, does not use the distributional Fourier transform. Several theorems concerning the particular linear transformations used to define the Laplace transforms are proved. All the results proved in one dimension are extended to the n-dimensional case, but proofs are presented only for those situations that require methods different from their one-dimensional analogs.
Price, D. R.↗
Elementary solutions of coupled model equations in the kinetic theory of gases
The method of elementary solutions is employed to solve two coupled integrodifferential equations sufficient for determining temperature-density effects in a linearized BGK model in the kinetic theory of gases. Full-range completeness and orthogonality theorems are proved for the developed normal modes and the infinite-medium Green's function is constructed as an illustration of the full-range formalism. The appropriate homogeneous matrix Riemann problem is discussed, and half-range completeness and orthogonality theorems are proved for a certain subset of the normal modes. The required existence and uniqueness theorems relevant to the H matrix, basic to the half-range analysis, are proved, and an accurate and efficient computational method is discussed. The half-space temperature-slip problem is solved analytically, and a highly accurate value of the temperature-slip coefficient is reported.
Kriese, J. T.↗
Ground simulation and tunnel blockage for a jet-flapped, basic STOL model tested to very high lift coefficients
Ground effects experiments and large/small-tunnel interference studies were carried out on a model with a 20-inch (50.8 cm) span wing. The wing, which includes a highly deflected knee-blown flap can be fitted with unflapped tips and slats. A low-mounted tailplane can be fitted to the aft fuselage. Three-component balance meaurements, made with a fixed ground equipped with a single boundary-layer blowing slot, were compared with datum, moving-ground results. Good comparisons were obtained up to model blowing momentum coefficients of approximately two, after which the particular floor blowing settings used proved insufficient to prevent floor separation in the vicinity of the model. Skin friction measurements, taken routinely along the floor centerline, proved invaluable during the analysis of results, and their use is recommended as input to determination of floor BLC setting. A careful investigation was made of pitching moments, including tail-on, close-to-ground cases, with favorable results. Drag proved the most sensitive to the change from a moving to the boundary-layer controlled ground.
Hackett, J. E.↗
Verification of Numerical Algorithms
The following strategy is suggested for specification and proof: (1) Defer the construction of a formal program specification with respect to I/O assertions unit the correctness of the program with respect to an abstract mathematical model of program intent is demonstrated. (2) Prove that an abstract machine (using infinite precision arithmetic) would compute that object exactly. (3) Prove that the computational sequences of arithmetic operations that occur in the abstract machine must be precisely the same at every step as those occurring on an actual machine (with finite precision arithmetic), executing the same program. (4) Use a Verification Conditions VC-generator that knows about the semantics of arithmetic operations to annotate the program with assertions that bound (or in some circumstances estimate) the difference between the actual machine state variables and the corresponding ones of the abstract machine. Construct the formal program specification by combining the verification conditions into theorems about computational error that can be proved with mechanical assistance.
Source record↗