Search NASA⌕ Search

SEARCH · Search NASA

Results for “String Matching”

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.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1995

Stereo-Based Region-Growing using String Matching

We present a novel stereo algorithm based on a coarse texture segmentation preprocessing phase. Matching is performed using a string comparison. Matching sub-strings correspond to matching sequences of textures. Inter-scanline clustering of matching sub-strings yields regions of matching texture. The shape of these regions yield information concerning object's height, width and azimuthal position relative to the camera pair. Hence, rather than the standard dense depth map, the output of this algorithm is a segmentation of objects in the scene. Such a format is useful for the integration of stereo with other sensor modalities on a mobile robotic platform. It is also useful for localization; the height and width of a detected object may be used for landmark recognition, while depth and relative azimuthal location determine pose. The algorithm does not rely on the monotonicity of order of image primitives. Occlusions, exposures, and foreshortening effects are not problematic. The algorithm can deal with certain types of transparencies. It is computationally efficient, and very amenable to parallel implementation. Further, the epipolar constraints may be relaxed to some small but significant degree. A version of the algorithm has been implemented and tested on various types of images. It performs best on random dot stereograms, on images with easily filtered backgrounds (as in synthetic images), and on real scenes with uncontrived backgrounds.

Mandelbaum, Robert↗
NASA NTRS2005

Deciding Termination for Ancestor Match- Bounded String Rewriting Systems

Termination of a string rewriting system can be characterized by termination on suitable recursively defined languages. This kind of termination criteria has been criticized for its lack of automation. In an earlier paper we have shown how to construct an automated termination criterion if the recursion is aligned with the rewrite relation. We have demonstrated the technique with Dershowitz's forward closure criterion. In this paper we show that a different approach is suitable when the recursion is aligned with the inverse of the rewrite relation. We apply this idea to Kurth's ancestor graphs and obtain ancestor match-bounded string rewriting systems. Termination is shown to be decidable for this class. The resulting method improves upon those based on match-boundedness or inverse match-boundedness.

Geser, Alfons↗
NASA NTRS2003

Match-bounded String Rewriting Systems

We introduce a new class of automated proof methods for the termination of rewriting systems on strings. The basis of all these methods is to show that rewriting preserves regular languages. To this end, letters are annotated with natural numbers, called match heights. If the minimal height of all positions in a redex is h+1 then every position in the reduct will get height h+1. In a match-bounded system, match heights are globally bounded. Using recent results on deleting systems, we prove that rewriting by a match-bounded system preserves regular languages. Hence it is decidable whether a given rewriting system has a given match bound. We also provide a sufficient criterion for the abence of a match-bound. The problem of existence of a match-bound is still open. Match-boundedness for all strings can be used as an automated criterion for termination, for match-bounded systems are terminating. This criterion can be strengthened by requiring match-boundedness only for a restricted set of strings, for instance the set of right hand sides of forward closures.

Geser, Alfons↗
NASA NTRS2014

Processing of ICARTT Data Files Using Fuzzy Matching and Parser Combinators

In this paper, the task of parsing and matching inconsistent, poorly formed text data through the use of parser combinators and fuzzy matching is discussed. An object-oriented implementation of the parser combinator technique is used to allow for a relatively simple interface for adapting base parsers. For matching tasks, a fuzzy matching algorithm with Levenshtein distance calculations is implemented to match string pair, which are otherwise difficult to match due to the aforementioned irregularities and errors in one or both pair members. Used in concert, the two techniques allow parsing and matching operations to be performed which had previously only been done manually.

Rutherford, Matthew T.↗
NASA NTRS1989

Shape matching utilizing indexed hypotheses generation and testing

An indexing mechanism is developed as part of an overall scheme called SMITH (shape matching utilizing indexed hypothesis generation and testing) for two-dimensional model-based object recognition. The approach is based on a dynamic programming implementation of attributed string matching, is computationally efficient, and works effectively for both nonoccluded and occluded shapes. Another advantage of this technique is that models may be inserted or deleted with relatively little cost.

Mehrotra, Rajiv↗
NASA NTRS1984

An overview of selected information storage and retrieval issues in computerized document processing

The rapid development of computerized information storage and retrieval techniques has introduced the possibility of extending the word processing concept to document processing. A major advantage of computerized document processing is the relief of the tedious task of manual editing and composition usually encountered by traditional publishers through the immense speed and storage capacity of computers. Furthermore, computerized document processing provides an author with centralized control, the lack of which is a handicap of the traditional publishing operation. A survey of some computerized document processing techniques is presented with emphasis on related information storage and retrieval issues. String matching algorithms are considered central to document information storage and retrieval and are also discussed.

Dominick, Wayne D.↗
NASA NTRS1989

Noiseless compression using non-Markov models

Adaptive data compression techniques can be viewed as consisting of a model specified by a database common to the encoder and decoder, an encoding rule and a rule for updating the model to ensure that the encoder and decoder always agree on the interpretation of the next transmission. The techniques which fit this framework range from run-length coding, to adaptive Huffman and arithmetic coding, to the string-matching techniques of Lempel and Ziv. The compression obtained by arithmetic coding is dependent on the generality of the source model. For many sources, an independent-letter model is clearly insufficient. Unfortunately, a straightforward implementation of a Markov model requires an amount of space exponential in the number of letters remembered. The Directed Acyclic Word Graph (DAWG) can be constructed in time and space proportional to the text encoded, and can be used to estimate the probabilities required for arithmetic coding based on an amount of memory which varies naturally depending on the encoded text. The tail of that portion of the text which was encoded is the longest suffix that has occurred previously. The frequencies of letters following these previous occurrences can be used to estimate the probability distribution of the next letter. Experimental results indicate that compression is often far better than that obtained using independent-letter models, and sometimes also significantly better than other non-independent techniques.

Blumer, Anselm↗
NASA NTRS2004

Termination Proofs for String Rewriting Systems via Inverse Match-Bounds

Annotating a letter by a number, one can record information about its history during a reduction. A string rewriting system is called match-bounded if there is a global upper bound to these numbers. In earlier papers we established match-boundedness as a strong sufficient criterion for both termination and preservation of regular languages. We show now that the string rewriting system whose inverse (left and right hand sides exchanged) is match-bounded, also have exceptional properties, but slightly different ones. Inverse match-bounded systems effectively preserve context-free languages; their sets of normalized strings and their sets of immortal strings are effectively regular. These sets of strings can be used to decide the normalization, the termination and the uniform termination problems of inverse match-bounded systems. We also show that the termination problem is decidable in linear time, and that a certain strong reachability problem is deciable, thus solving two open problems of McNaughton's.

Butler, Ricky↗
NASA NTRS2018

Seasonal Monitoring of Melt and Accumulation Within the Deep Percolation Zone of the Greenland Ice Sheet and Comparison with Simulations of Regional Climate Modeling

Increasing melt over the Greenland Ice Sheet (GrIS) recorded over the past several years has resulted in significant changes of the percolation regime of the ice sheet. It remains unclear whether Greenland's percolation zone will act as a meltwater buffer in the near future through gradually filling all pore space or if near-surface refreezing causes the formation of impermeable layers, which provoke lateral runoff. Homogeneous ice layers within perennial firn, as well as near-surface ice layers of several meter thickness have been observed in firn cores. Because firn coring is a destructive method, deriving stratigraphic changes in firn and allocation of summer melt events is challenging. To overcome this deficit and provide continuous data for model evaluations on snow and firn density, temporal changes in liquid water content and depths of water infiltration, we installed an upward-looking radar system (upGPR) 3.4 m below the snow surface in May 2016 close to Camp Raven (66.4779 deg N, 46.2856 deg W) at 2120 m a.s.l. The radar is capable of quasi-continuously monitoring changes in snow and firn stratigraphy, which occur above the antennas. For summer 2016, we observed four major melt events, which routed liquid water into various depths beneath the surface. The last event in mid-August resulted in the deepest percolation down to about 2.3 m beneath the surface. Comparisons with simulations from the regional climate model MAR are in very good agreement in terms of seasonal changes in accumulation and timing of onset of melt. However, neither bulk density of near-surface layers nor the amounts of liquid water and percolation depths predicted by MAR correspond with upGPR data. Radar data and records of a nearby thermistor string, in contrast, matched very well for both timing and depth of temperature changes and observed water percolations. All four melt events transferred a cumulative mass of 56 kg/(sq. m) into firn beneath the summer surface of 2015. We find that continuous observations of liquid water content, percolation depths and rates for the seasonal mass fluxes are sufficiently accurate to provide valuable information for validation of model approaches and help to develop a better understanding of liquid water retention and percolation in perennial firn.

Heilig, Achim↗
NASA NTRS2019

All-Sky Search for Short Gravitational-Wave Bursts in the Second Advanced LIGO and Advanced Virgo Run

We present the results of a search for short-duration gravitational-wave transients in the data from the second observing run of Advanced LIGO and Advanced Virgo. We search for gravitational-wave transients with a duration of milliseconds to approximately one second in the 32–4096 Hz frequency band with minimal assumptions about the signal properties, thus targeting a wide variety of sources. We also perform a matched-filter search for gravitational-wave transients from cosmic string cusps for which the waveform is well modeled. The unmodeled search detected gravitational waves from several binary black hole mergers which have been identified by previous analyses. No other significant events have been found by either the unmodeled search or the cosmic string search. We thus present the search sensitivities for a variety of signal waveforms and report upper limits on the source rate density as a function of the characteristic frequency of the signal. These upper limits are a factor of 3 lower than the first observing run, with a 50% detection probability for gravitational-wave emissions with energies of ∼10−9 𝑀⊙⁢𝑐2 at 153 Hz. For the search dedicated to cosmic string cusps we consider several loop distribution models, and present updated constraints from the same search done in the first observing run.

B P Abbott↗
NASA NTRS2017

North Polar Radiative Flux Variability from 2002 Through 2014

NASA's Clouds and the Earth's Radiant Energy System (CERES) project produces the SYN1Deg data product. SYN1deg provides global, 1deg gridded, hourly estimates of Top of Atmosphere (TOA) (CERES observations and calculations) and atmospheric and surface radiative flux (calculations). Examples of 12 year North Polar averages of some variables are shown to the right. Given recent interest in polar science we focus here on TOA and Surface validation of calculated irradiant fluxes. TOA upward longwave irradiance calculations match the CERES observations well both spatially and temporally with correlations remaining strong through PC 6. Compare SYN1Deg Calculations & Meteorological Teleconnections. TOA reflected shortwave irradiance calculations match the CERES observations well both spatially and temporally with correlations remaining string through PC 7. Comparing SYN1Deg calculations to teleconnection patterns requires expanding the area to 30N for EOF analyses. Correlating the Principal Components of various variables to teleconnection time series indicates which variable is most highly correlated with which teleconnection signal. The tables indicate the Pacific North American Oscillation is most correlated to the OLR EOF 1, and the North American Oscillation is correlated most closely to surface LW flux down EOF 1.

Rutan, David↗
NASA NTRS1982

Parrallel Connections Would Improve Array Reliability

Hexagonnally-close-packed round solar cells are interconnected in series strings. Parallel contacts between cells at equipotential in adjacent series strings insure redundant current paths to relieve adverse effects of cell failures and mismatches. Parallel connections carry no current if cells are matched and functioning normally. If cell fails, tabs carry current to bypass inoperative cell.

Crouthamel, M. S.↗
NASA NTRS2010

Operating and Managing a Backup Control Center

Due to the criticality of continuous mission operations, some control centers must plan for alternate locations in the event an emergency shuts down the primary control center. Johnson Space Center (JSC) in Houston, Texas is the Mission Control Center (MCC) for the International Space Station (ISS). Due to Houston s proximity to the Gulf of Mexico, JSC is prone to threats from hurricanes which could cause flooding, wind damage, and electrical outages to the buildings supporting the MCC. Marshall Space Flight Center (MSFC) has the capability to be the Backup Control Center for the ISS if the situation is needed. While the MSFC Huntsville Operations Support Center (HOSC) does house the BCC, the prime customer and operator of the ISS is still the JSC flight operations team. To satisfy the customer and maintain continuous mission operations, the BCC has critical infrastructure that hosts ISS ground systems and flight operations equipment that mirrors the prime mission control facility. However, a complete duplicate of Mission Control Center in another remote location is very expensive to recreate. The HOSC has infrastructure and services that MCC utilized for its backup control center to reduce the costs of a somewhat redundant service. While labor talents are equivalent, experiences are not. Certain operations are maintained in a redundant mode, while others are simply maintained as single string with adequate sparing levels of equipment. Personnel at the BCC facility must be trained and certified to an adequate level on primary MCC systems. Negotiations with the customer were done to match requirements with existing capabilities, and to prioritize resources for appropriate level of service. Because some of these systems are shared, an activation of the backup control center will cause a suspension of scheduled HOSC activities that may share resources needed by the BCC. For example, the MCC is monitoring a hurricane in the Gulf of Mexico. As the threat to MCC increases, HOSC must begin a phased activation of the BCC, while working resource conflicts with normal HOSC activities. In a long duration outage to the MCC, this could cause serious impacts to the BCC host facility s primary mission support activities. This management of a BCC is worked based on customer expectations and negotiations done before emergencies occur. I.

Marsh, Angela L.↗
NASA NTRS1999

Lightweight Battery Charge Regulator Used to Track Solar Array Peak Power

A battery charge regulator based on the series-connected boost regulator (SCBR) technology has been developed for high-voltage spacecraft applications. The SCBR regulates the solar array power during insolation to prevent battery overcharge or undercharge conditions. It can also be used to provide regulated battery output voltage to spacecraft loads if necessary. This technology uses industry-standard dc-dc converters and a unique interconnection to provide size, weight, efficiency, fault tolerance, and modularity benefits over existing systems. The high-voltage SCBR shown in the photograph has demonstrated power densities of over 1000 watts per kilogram (W/kg). Using four 150-W dc-dc converter modules, it can process 2500 W of power at 120 Vdc with a minimum input voltage of 90 Vdc. Efficiency of the SCBR was 94 to 98 percent over the entire operational range. Internally, the unit is made of two separate SCBR s, each with its own analog control circuitry, to demonstrate the modularity of the technology. The analog controllers regulate the output current and incorporate the output voltage limit with active current sharing between the two units. They also include voltage and current telemetry, on/off control, and baseplate temperature sensors. For peak power tracking, the SCBR was connected to a LabView-based data acquisition system for telemetry and control. A digital control algorithm for tracking the peak power point of a solar array was developed using the principle of matching the source impedance with the load impedance for maximum energy transfer. The algorithm was successfully demonstrated in a simulated spacecraft electrical system at the Boeing PhantomWorks High Voltage Test Facility in Seattle, Washington. The system consists of a 42-string, high-voltage solar array simulator, a 77-cell, 80-ampere-hour (A-hr) nickel-hydrogen battery, and a constant power-load module. The SCBR and the LabView control algorithm successfully tracked the solar array peak power point through various load transients, including sunlight discharge transients when the total load exceeded the maximum solar array output power.

Soeder, James F.↗
NASA NTRS1974

Refractive index of plant cell walls

Air was replaced with media of higher refractive indices by vacuum infiltration in leaves of cucumber, blackeye pea, tomato, and string bean plants, and reflectance of noninfiltrated and infiltrated leaves was spectrophotometrically measured. Infiltrated leaves reflected less light than noninfiltrated leaves over the 500-2500-nm wavelength interval because cell wall-air interfaces were partly eliminated. Minimal reflectance should occur when the average refractive index of plant cell walls was matched by the infiltrating fluid. Although refractive indices that resulted in minimal reflectance differed among the four plant genera, an average value of 1.425 approximates the refractive index of plant cell walls for the four plant genera.

Gausman, H. W.↗
NASA NTRS2003

Antiproton Production by CR on Air Nuclei

Recent measurements of the cosmic ray (CR) antiproton flux have been shown to challenge existing CR propagation models. In particular, the conventional reacceleration model designed to match secondary/primary nuclei ratios produces too few antiprotons. Recently there appear some indications that the atmospheric contribution to antiproton production is considerably underestimated, which implies that antiproton CR flux might be lower. This may be the primary reason of the discrepancy discovered in CR propagation. We use the Los Alamos version of the Quark-Gluon String Model code LAQGSM together with available data on antiproton production on nuclei to analyse the accuracy of existing parameterizations of antiproton production cross section. The LAQGSM model has been shown to reproduce well nuclear reactions and hadronic data in the range 0.01-800 GeV/nucleon.

Maskalenko, I. V.↗
NASA NTRS2005

EXTENSIBLE DATABASE FRAMEWORK FOR MANAGEMENT OF UNSTRUCTURED AND SEMI-STRUCTURED DOCUMENTS

Method and system for querying a collection of Unstructured or semi-structured documents to identify presence of, and provide context and/or content for, keywords and/or keyphrases. The documents are analyzed and assigned a node structure, including an ordered sequence of mutually exclusive node segments or strings. Each node has an associated set of at least four, five or six attributes with node information and can represent a format marker or text, with the last node in any node segment usually being a text node. A keyword (or keyphrase) is specified. and the last node in each node segment is searched for a match with the keyword. When a match is found at a query node, or at a node determined with reference to a query node, the system displays the context andor the content of the query node.

Gawdiak, Yuri O.↗
NASA NTRS2006

NASA Taxonomies for Searching Problem Reports and FMEAs

Many types of hazard and risk analyses are used during the life cycle of complex systems, including Failure Modes and Effects Analysis (FMEA), Hazard Analysis, Fault Tree and Event Tree Analysis, Probabilistic Risk Assessment, Reliability Analysis and analysis of Problem Reporting and Corrective Action (PRACA) databases. The success of these methods depends on the availability of input data and the analysts knowledge. Standard nomenclature can increase the reusability of hazard, risk and problem data. When nomenclature in the source texts is not standard, taxonomies with mapping words (sets of rough synonyms) can be combined with semantic search to identify items and tag them with metadata based on a rich standard nomenclature. Semantic search uses word meanings in the context of parsed phrases to find matches. The NASA taxonomies provide the word meanings. Spacecraft taxonomies and ontologies (generalization hierarchies with attributes and relationships, based on terms meanings) are being developed for types of subsystems, functions, entities, hazards and failures. The ontologies are broad and general, covering hardware, software and human systems. Semantic search of Space Station texts was used to validate and extend the taxonomies. The taxonomies have also been used to extract system connectivity (interaction) models and functions from requirements text. Now the Reconciler semantic search tool and the taxonomies are being applied to improve search in the Space Shuttle PRACA database, to discover recurring patterns of failure. Usual methods of string search and keyword search fall short because the entries are terse and have numerous shortcuts (irregular abbreviations, nonstandard acronyms, cryptic codes) and modifier words cannot be used in sentence context to refine the search. The limited and fixed FMEA categories associated with the entries do not make the fine distinctions needed in the search. The approach assigns PRACA report titles to problem classes in the taxonomy. Each ontology class includes mapping words - near-synonyms naming different manifestations of that problem class. The mapping words for Problems, Entities and Functions are converted to a canonical form plus any of a small set of modifier words (e.g. non-uniformity NOT + UNIFORM.) The report titles are parsed as sentences if possible, or treated as a flat sequence of word tokens if parsing fails. When canonical forms in the title match mapping words, the PRACA entry is associated with the corresponding Problem, Entity or Function in the ontology. The user can search for types of failures associated with types of equipment, clustering by type of problem (e.g., all bearings found with problems of being uneven: rough, irregular, gritty ). The results could also be used for tagging PRACA report entries with rich metadata. This approach could also be applied to searching and tagging failure modes, failure effects and mitigations in FMEAs. In the pilot work, parsing 52K+ truncated titles (the test cases that were available), has resulted in identification of both a type of equipment and type of problem in about 75% of the cases. The results are displayed in a manner analogous to Google search results. The effort has also led to the enrichment of the taxonomy, adding some new categories and many new mapping words. Further work would make enhancements that have been identified for improving the clustering and further reducing the false alarm rate. (In searching for recurring problems, good clustering is more important than reducing false alarms). Searching complete PRACA reports should lead to immediate improvement.

Malin, Jane T.↗