Search NASA⌕ Search

SEARCH · Search NASA

Results for “automata”

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 145 records · Page 8
All sourcesNASA NTRSDOE OSTI
NASA NTRS1990

Theory of multicolor lattice gas - A cellular automaton Poisson solver

The present class of models for cellular automata involving a quiescent hydrodynamic lattice gas with multiple-valued passive labels termed 'colors', the lattice collisions change individual particle colors while preserving net color. The rigorous proofs of the multicolor lattice gases' essential features are rendered more tractable by an equivalent subparticle representation in which the color is represented by underlying two-state 'spins'. Schemes for the introduction of Dirichlet and Neumann boundary conditions are described, and two illustrative numerical test cases are used to verify the theory. The lattice gas model is equivalent to a Poisson equation solution.

Chen, H.↗
NASA NTRS1990

Partitioning of regular computation on multiprocessor systems

Problem partitioning of regular computation over two dimensional meshes on multiprocessor systems is examined. The regular computation model considered involves repetitive evaluation of values at each mesh point with local communication. The computational workload and the communication pattern are the same at each mesh point. The regular computation model arises in numerical solutions of partial differential equations and simulations of cellular automata. Given a communication pattern, a systematic way to generate a family of partitions is presented. The influence of various partitioning schemes on performance is compared on the basis of computation to communication ratio.

Lee, Fung F.↗
NASA NTRS1990

Concurrency and discrete event control

Much of discrete event control theory has been developed within the framework of automata and formal languages. An alternative approach inspired by the theories of process-algebra as developed in the computer science literature is presented. The framework, which rests on a new formalism of concurrency, can adequately handle nondeterminism and can be used for analysis of a wide range of discrete event phenomena.

Heymann, Michael↗
NASA NTRS1990

Astrophysical fractals - An overview and prospects

Different astrophysical circumstances under which fractal structures have been identified so far, or are likely to be identified in the future, are reviewed. The observed fractals can be classified into 2 main groups: (1) fractal configurations in space-time, materializing as fractals defined over the time axis at a given position in space, or over the physical configuration space at a fixed instant in time; and (2) fractals in parameter spaces. The theoretical interpretation of the origin of the spatial fractal geometry of the most conspicuous 'irregular' astronomical bodies is still wanting in the context of standard continuum models. In contrast, the less conventional discrete models (cellular automata) naturally produce such spatially fractal structures.

Perdang, J.↗
NASA NTRS1991

An introduction to autonomous control systems

The functions, characteristics, and benefits of autonomous control are outlined. An autonomous control functional architecture for future space vehicles that incorporates the concepts and characteristics described is presented. The controller is hierarchical, with an execution level (the lowest level), coordination level (middle level), and management and organization level (highest level). The general characteristics of the overall architecture, including those of the three levels, are explained, and an example to illustrate their functions is given. Mathematical models for autonomous systems, including 'logical' discrete event system models, are discussed. An approach to the quantitative, systematic modeling, analysis, and design of autonomous controllers is also discussed. It is a hybrid approach since it uses conventional analysis techniques based on difference and differential equations and new techniques for the analysis of the systems described with a symbolic formalism such as finite automata. Some recent results from the areas of planning and expert systems, machine learning, artificial neural networks, and the area restructurable controls are briefly outlined.

Antsaklis, Panos J.↗
NASA NTRS1990

Automatic Management of Parallel and Distributed System Resources

Viewgraphs on automatic management of parallel and distributed system resources are presented. Topics covered include: parallel applications; intelligent management of multiprocessing systems; performance evaluation of parallel architecture; dynamic concurrent programs; compiler-directed system approach; lattice gaseous cellular automata; and sparse matrix Cholesky factorization.

Yan, Jerry↗
NASA NTRS1993

Simple systems that exhibit self-directed replication

Biological experience and intuition suggest that self-replication is an inherently complex phenomenon, and early cellular automata models support that conception. More recently, simpler computational models of self-directed replication called sheathed loops have been developed. It is shown here that 'unsheathing' these structures and altering certain assumptions about the symmetry of their components leads to a family of nontrivial self-replicating structures some substantially smaller and simpler than those previously reported. The dependence of replication time and transition function complexity on initial structure size, cell state symmetry, and neighborhood are examined. These results support the view that self-replication is not an inherently complex phenomenon but rather an emergent property arising from local interactions in systems that can be much simpler than is generally believed.

Reggia, James A.↗
NASA NTRS1994

Efficient massively parallel simulation of dynamic channel assignment schemes for wireless cellular communications

Fast, efficient parallel algorithms are presented for discrete event simulations of dynamic channel assignment schemes for wireless cellular communication networks. The driving events are call arrivals and departures, in continuous time, to cells geographically distributed across the service area. A dynamic channel assignment scheme decides which call arrivals to accept, and which channels to allocate to the accepted calls, attempting to minimize call blocking while ensuring co-channel interference is tolerably low. Specifically, the scheme ensures that the same channel is used concurrently at different cells only if the pairwise distances between those cells are sufficiently large. Much of the complexity of the system comes from ensuring this separation. The network is modeled as a system of interacting continuous time automata, each corresponding to a cell. To simulate the model, conservative methods are used; i.e., methods in which no errors occur in the course of the simulation and so no rollback or relaxation is needed. Implemented on a 16K processor MasPar MP-1, an elegant and simple technique provides speedups of about 15 times over an optimized serial simulation running on a high speed workstation. A drawback of this technique, typical of conservative methods, is that processor utilization is rather low. To overcome this, new methods were developed that exploit slackness in event dependencies over short intervals of time, thereby raising the utilization to above 50 percent and the speedup over the optimized serial code to about 120 times.

Greenberg, Albert G.↗
NASA NTRS1994

A novel computational method to simulate non-enzymatic self-replication

Non-enzymatic, template-directed synthesis of oligonucleotides has been extensively studied in the laboratory as a model to understand the kind of chemical processes that might have contributed to the origin of life on Earth. Several oligonucleotides have been shown to catalyze the synthesis of their complements from activated mononucleotides; however, a restricted number of them have been found to self-replicate. Recently we developed an efficient modified cellular automata method that supports the study of self-replicating oligonucleotides. With this method the oligonucleotide molecules are represented as active cells imbedded in a two-dimensional array of inactive cells symbolizing the environment. Random movements and probability-governed chemical reactions occurring in a cellular space can effectively simulate the experimental behavior observed in self-directed replication of oligonucleotides.

Navarro-Gonzalez, Rafael↗
NASA NTRS1994

Climatic, eustatic, and tectnoic controls on Quarternary deposits and landforms, Red Sea coast, Egypt

The degree to which local climatic variations, eustatic sea level fluctuations, and tectonic uplift have influenced the development of Quaternary marine and fluvial landforms and deposits along the Red Sea coast, Eastern Desert, was investigated using a combination of remote sensing and field data, age determinations of corals, and numerical simulations. False color composites generated from Landsat Thematic Mapper and SPOT image data, digital elevation models derived from sterophotogrammetric analysis of SPOT data, and field observations document that a approximately 10-km wide swath inland from the coast is covered in many places with coalescing alluvial fans of Quaternary age. Wadis cutting through the fans exhibit several pairs of fluvial terraces, and wadi walls expose alluvium interbedded with corraline limestone deposits Further, three distinct coral terraces are evident along the coatline. Climatic, eustatic, and tectonic uplift controls on the overall system were simulated using a cellular automata algorithm with the following characteristics: (1) uplift as a function of position and time, as defined by the elevations and ages of corals; (2) climatic variations driven by insolation changes associated with Milankovitch cycles; (3) sea level fluctuations based on U/Th ages of coral terraces and eustatic data; and (4) parametrized fluvial erosion and deposition. Results imply that the fans and coralline limestones were generated in a setting in which the tectonic uplift rate decreased over the Quarternary to negligible values at present. Coralline limestones formed furing eustatic highstands when alluvium was trapped uspstream and wadis filled with debris. During lowstands, wadis cut into sedimentary deposits; coupled with continuing uplift, fans were dissected, leaving remnant surfaces, and wadi-related terraces were generated by down cutting. Only landforms from the past three to four eustatic sea level cycles (i.e., approximately 300 to 400 kyr) are likely to have survived erosion and deposition associated with fluvial processes.

Arvidson, Raymond↗
NASA NTRS1995

Model checking

Automatic formal verification methods for finite-state systems, also known as model-checking, successfully reduce labor costs since they are mostly automatic. Model checkers explicitly or implicitly enumerate the reachable state space of a system, whose behavior is described implicitly, perhaps by a program or a collection of finite automata. Simple properties, such as mutual exclusion or absence of deadlock, can be checked by inspecting individual states. More complex properties, such as lack of starvation, require search for cycles in the state graph with particular properties. Specifications to be checked may consist of built-in properties, such as deadlock or 'unspecified receptions' of messages, another program or implicit description, to be compared with a simulation, bisimulation, or language inclusion relation, or an assertion in one of several temporal logics. Finite-state verification tools are beginning to have a significant impact in commercial designs. There are many success stories of verification tools finding bugs in protocols or hardware controllers. In some cases, these tools have been incorporated into design methodology. Research in finite-state verification has been advancing rapidly, and is showing no signs of slowing down. Recent results include probabilistic algorithms for verification, exploitation of symmetry and independent events, and the use symbolic representations for Boolean functions and systems of linear inequalities. One of the most exciting areas for further research is the combination of model-checking with theorem-proving methods.

Dill, David L.↗
NASA NTRS1998

Multidisciplinary Design Optimization (MDO) Methods: Their Synergy with Computer Technology in Design Process

The paper identifies speed, agility, human interface, generation of sensitivity information, task decomposition, and data transmission (including storage) as important attributes for a computer environment to have in order to support engineering design effectively. It is argued that when examined in terms of these attributes the presently available environment can be shown to be inadequate a radical improvement is needed, and it may be achieved by combining new methods that have recently emerged from multidisciplinary design optimization (MDO) with massively parallel processing computer technology. The caveat is that, for successful use of that technology in engineering computing, new paradigms for computing will have to be developed - specifically, innovative algorithms that are intrinsically parallel so that their performance scales up linearly with the number of processors. It may be speculated that the idea of simulating a complex behavior by interaction of a large number of very simple models may be an inspiration for the above algorithms, the cellular automata are an example. Because of the long lead time needed to develop and mature new paradigms, development should be now, even though the widespread availability of massively parallel processing is still a few years away.

Sobieszczanski-Sobieski, Jaroslaw↗
NASA NTRS1999

Multidisciplinary Design Optimisation (MDO) Methods: Their Synergy with Computer Technology in the Design Process

The paper identifies speed, agility, human interface, generation of sensitivity information, task decomposition, and data transmission (including storage) as important attributes for a computer environment to have in order to support engineering design effectively. It is argued that when examined in terms of these attributes the presently available environment can be shown to be inadequate. A radical improvement is needed, and it may be achieved by combining new methods that have recently emerged from multidisciplinary design optimisation (MDO) with massively parallel processing computer technology. The caveat is that, for successful use of that technology in engineering computing, new paradigms for computing will have to be developed - specifically, innovative algorithms that are intrinsically parallel so that their performance scales up linearly with the number of processors. It may be speculated that the idea of simulating a complex behaviour by interaction of a large number of very simple models may be an inspiration for the above algorithms; the cellular automata are an example. Because of the long lead time needed to develop and mature new paradigms, development should begin now, even though the widespread availability of massively parallel processing is still a few years away.

Sobieszczanski-Sobieski, Jaroslaw↗
NASA NTRS1999

Low-Speed Investigation of Upper-Surface Leading-Edge Blowing on a High-Speed Civil Transport Configuration

The paper identifies speed, agility, human interface, generation of sensitivity information, task decomposition, and data transmission (including storage) as important attributes for a computer environment to have in order to support engineering design effectively. It is argued that when examined in terms of these attributes the presently available environment can be shown to be inadequate. A radical improvement is needed, and it may be achieved by combining new methods that have recently emerged from multidisciplinary design optimisation (MDO) with massively parallel processing computer technology. The caveat is that, for successful use of that technology in engineering computing, new paradigms for computing will have to be developed - specifically, innovative algorithms that are intrinsically parallel so that their performance scales up linearly with the number of processors. It may be speculated that the idea of simulating a complex behaviour by interaction of a large number of very simple models may be an inspiration for the above algorithms; the cellular automata are an example. Because of the long lead time needed to develop and mature new paradigms, development should begin now, even though the widespread availability of massively parallel processing is still a few years away.

Banks, Daniel W.↗
NASA NTRS1997

[Development of New Mathematical Methodology in Air Traffic Control for the Analysis of Hybrid Systems]

The aim of this research is to develop new mathematical methodology for the analysis of hybrid systems of the type involved in Air Traffic Control (ATC) problems. Two directions of investigation were initiated. The first used the methodology of nonlinear generalized functions, whose mathematical foundations were initiated by Colombeau and developed further by Oberguggenberger; it has been extended to apply to ordinary differential. Systems of the type encountered in control in joint work with the PI and M. Oberguggenberger. This involved a 'mixture' of 'continuous' and 'discrete' methodology. ATC clearly involves mixtures of two sorts of mathematical problems: (1) The 'continuous' dynamics of a standard control type described by ordinary differential equations (ODE) of the form: {dx/dt = f(x, u)} and (2) the discrete lattice dynamics involved of cellular automata. Most of the CA literature involves a discretization of a partial differential equation system of the type encountered in physics problems (e.g. fluid and gas problems). Both of these directions requires much thinking and new development of mathematical fundamentals before they may be utilized in the ATC work. Rather than consider CA as 'discretization' of PDE systems, I believe that the ATC applications will require a completely different and new mathematical methodology, a sort of discrete analogue of jet bundles and/or the sheaf-theoretic techniques to topologists. Here too, I have begun work on virtually 'virgin' mathematical ground (at least from an 'applied' point of view) which will require considerable preliminary work.

Hermann, Robert↗
NASA NTRS1994

Design of Flight Vehicle Management Systems

As the operation of large systems becomes ever more dependent on extensive automation, the need for an effective solution to the problem of design and validation of the underlying software becomes more critical. Large systems possess much detailed structure, typically hierarchical, and they are hybrid. Information processing at the top of the hierarchy is by means of formal logic and sentences; on the bottom it is by means of simple scalar differential equations and functions of time; and in the middle it is by an interacting mix of nonlinear multi-axis differential equations and automata, and functions of time and discrete events. The lecture will address the overall problem as it relates to flight vehicle management, describe the middle level, and offer a design approach that is based on Differential Geometry and Discrete Event Dynamic Systems Theory.

Meyer, George↗
NASA NTRS1995

Nonlinear Control and Discrete Event Systems

As the operation of large systems becomes ever more dependent on extensive automation, the need for an effective solution to the problem of design and validation of the underlying software becomes more critical. Large systems possesses much detailed structure, typically hierarchical, and they are hybrid. Information processing at the top of the hierarchy is by means of formal logic and sentences; on the bottom it is by means of simple scalar differential equations and functions of time; and in the middle it is by an interacting mix of nonlinear multi-axis differential equations and automata, and functions of time and discrete events. The lecture will address the overall problem as it relates to flight vehicle management, describe the middle level, and offer a design approach that is based on Differential Geometry and Discrete Event Dynamic Systems Theory.

Meyer, George↗
NASA NTRS1999

Unifying Model-Based and Reactive Programming within a Model-Based Executive

Real-time, model-based, deduction has recently emerged as a vital component in AI's tool box for developing highly autonomous reactive systems. Yet one of the current hurdles towards developing model-based reactive systems is the number of methods simultaneously employed, and their corresponding melange of programming and modeling languages. This paper offers an important step towards unification. We introduce RMPL, a rich modeling language that combines probabilistic, constraint-based modeling with reactive programming constructs, while offering a simple semantics in terms of hidden state Markov processes. We introduce probabilistic, hierarchical constraint automata (PHCA), which allow Markov processes to be expressed in a compact representation that preserves the modularity of RMPL programs. Finally, a model-based executive, called Reactive Burton is described that exploits this compact encoding to perform efficIent simulation, belief state update and control sequence generation.

Williams, Brian C.↗