On Undecidable Dynamical Properties of Reversible One-Dimensional Cellular Automata

Cellular automata are models for massively parallel computation. A cellular automaton consists of cells which are arranged in some kind of regular lattice and a local update rule which updates the state of each cell according to the states of the cell's neighbors on each step of the computation. This work focuses on reversible one-dimensional cellular automata in which the cells are arranged in a two-way in_nite line and the computation is reversible, that is, the previous states of the cells can be derived from the current ones. In this work it is shown that several properties of reversible one-dimensional cellular automata are algorithmically undecidable, that is, there exists no algorithm that would tell whether a given cellular automaton has the property or not. It is shown that the tiling problem of Wang tiles remains undecidable even in some very restricted special cases. It follows that it is undecidable whether some given states will always appear in computations by the given cellular automaton. It also follows that a weaker form of expansivity, which is a concept of dynamical systems, is an undecidable property for reversible one-dimensional cellular automata. It is shown that several properties of dynamical systems are undecidable for reversible one-dimensional cellular automata. It shown that sensitivity to initial conditions and topological mixing are undecidable properties. Furthermore, non-sensitive and mixing cellular automata are recursively inseparable. It follows that also chaotic behavior is an undecidable property for reversible one-dimensional cellular automata.

Linear-quadratic optimal control of descriptor systems

In recent years the analysis and synthesis of (mechanical) control systems in descriptor form has been established. This general description of dynamical systems is important for many applications in mechanics and mechatronics, in electrical and electronic engineering, and in chemical engineering as well. This contribution deals with linear mechanical descriptor systems and its control design with respect to a quadratic performance criterion. Here, the notion of properness plays an important role whether the standard Riccati approach can be applied as usual or not. Properness and non-properness distinguish between the cases if the descriptor system is exclusively governed by the control input or by its higher-order time-derivatives additionally. In the unusual case of non-proper systems a quite different problem of optimal control design has to be considered. Both cases will be solved completely.

On state and parameter estimation in chaotic systems

State-of-the-art predictions of atmospheric states rely on large-scale numerical models of chaotic systems. This dissertation studies numerical methods for state and parameter estimation in such systems. The motivation comes from weather and climate models and a methodological perspective is adopted. The dissertation comprises three sections: state estimation, parameter estimation and chemical data assimilation with real atmospheric satellite data. In the state estimation part of this dissertation, a new filtering technique based on a combination of ensemble and variational Kalman filtering approaches, is presented, experimented and discussed. This new filter is developed for large-scale Kalman filtering applications. In the parameter estimation part, three different techniques for parameter estimation in chaotic systems are considered. The methods are studied using the parameterized Lorenz 95 system, which is a benchmark model for data assimilation. In addition, a dilemma related to the uniqueness of weather and climate model closure parameters is discussed. In the data-oriented part of this dissertation, data from the Global Ozone Monitoring by Occultation of Stars (GOMOS) satellite instrument are considered and an alternative algorithm to retrieve atmospheric parameters from the measurements is presented. The validation study presents first global comparisons between two unique satellite-borne datasets of vertical profiles of nitrogen trioxide (NO3), retrieved using GOMOS and Stratospheric Aerosol and Gas Experiment III (SAGE III) satellite instruments. The GOMOS NO3 observations are also considered in a chemical state estimation study in order to retrieve stratospheric temperature profiles. The main result of this dissertation is the consideration of likelihood calculations via Kalman filtering outputs. The concept has previously been used together with stochastic differential equations and in time series analysis. In this work, the concept is applied to chaotic dynamical systems and used together with Markov chain Monte Carlo (MCMC) methods for statistical analysis. In particular, this methodology is advocated for use in numerical weather prediction (NWP) and climate model applications. In addition, the concept is shown to be useful in estimating the filter-specific parameters related, e.g., to model error covariance matrix parameters.

Studies on the Effect of Randomness on the Synchronization of Coupled Systems and on the Dynamics of Intermittently driven systems

Nonlinear dynamics has emerged into a prominent area of research in the past few Decades.Turbulence, Pattern formation,Multistability etc are some of the important areas of research in nonlinear dynamics apart from the study of chaos.Chaos refers to the complex evolution of a deterministic system, which is highly sensitive to initial conditions. The study of chaos theory started in the modern sense with the investigations of Edward Lorentz in mid 60's. Later developments in this subject provided systematic development of chaos theory as a science of deterministic but complex and unpredictable dynamical systems. This thesis deals with the effect of random fluctuations with its associated characteristic timescales on chaos and synchronization. Here we introduce the concept of noise, and two familiar types of noise are discussed. The classifications and representation of white and colored noise are introduced. Based on this we introduce the concept of randomness that we deal with as a variant of the familiar concept of noise. The dynamical systems introduced are the Rossler system, directly modulated semiconductor lasers and the Harmonic oscillator. The directly modulated semiconductor laser being not a much familiar dynamical system, we have included a detailed introduction to its relevance in Chaotic encryption based cryptography in communication. We show that the effect of a fluctuating parameter mismatch on synchronization is to destroy the synchronization. Further we show that the relation between synchronization error and timescales can be found empirically but there are also cases where this is not possible. Studies show that under the variation of the parameters, the system becomes chaotic, which appears to be the period doubling route to chaos.

Development and Evaluation of Blind Identification Techniques for Nonlinear Systems

Identification and Control of Non‐linear dynamical systems are challenging problems to the control engineers.The topic is equally relevant in communication,weather prediction ,bio medical systems and even in social systems,where nonlinearity is an integral part of the system behavior.Most of the real world systems are nonlinear in nature and wide applications are there for nonlinear system identification/modeling.The basic approach in analyzing the nonlinear systems is to build a model from known behavior manifest in the form of system output.The problem of modeling boils down to computing a suitably parameterized model,representing the process.The parameters of the model are adjusted to optimize a performanace function,based on error between the given process output and identified process/model output.While the linear system identification is well established with many classical approaches,most of those methods cannot be directly applied for nonlinear system identification.The problem becomes more complex if the system is completely unknown but only the output time series is available.Blind recognition problem is the direct consequence of such a situation.The thesis concentrates on such problems.Capability of Artificial Neural Networks to approximate many nonlinear input-output maps makes it predominantly suitable for building a function for the identification of nonlinear systems,where only the time series is available.The literature is rich with a variety of algorithms to train the Neural Network model.A comprehensive study of the computation of the model parameters,using the different algorithms and the comparison among them to choose the best technique is still a demanding requirement from practical system designers,which is not available in a concise form in the literature.The thesis is thus an attempt to develop and evaluate some of the well known algorithms and propose some new techniques,in the context of Blind recognition of nonlinear systems.It also attempts to establish the relative merits and demerits of the different approaches.comprehensiveness is achieved in utilizing the benefits of well known evaluation techniques from statistics. The study concludes by providing the results of implementation of the currently available and modified versions and newly introduced techniques for nonlinear blind system modeling followed by a comparison of their performance.It is expected that,such comprehensive study and the comparison process can be of great relevance in many fields including chemical,electrical,biological,financial and weather data analysis.Further the results reported would be of immense help for practical system designers and analysts in selecting the most appropriate method based on the goodness of the model for the particular context.

Studies on the universal parameters and onset of chaos in dissipative systems

It has become clear over the last few years that many deterministic dynamical systems described by simple but nonlinear equations with only a few variables can behave in an irregular or random fashion. This phenomenon, commonly called deterministic chaos, is essentially due to the fact that we cannot deal with infinitely precise numbers. In these systems trajectories emerging from nearby initial conditions diverge exponentially as time evolves)and therefore)any small error in the initial measurement spreads with time considerably, leading to unpredictable and chaotic behaviour The thesis work is mainly centered on the asymptotic behaviour of nonlinear and nonintegrable dissipative dynamical systems. It is found that completely deterministic nonlinear differential equations describing such systems can exhibit random or chaotic behaviour. Theoretical studies on this chaotic behaviour can enhance our understanding of various phenomena such as turbulence, nonlinear electronic circuits, erratic behaviour of heart and brain, fundamental molecular reactions involving DNA, meteorological phenomena, fluctuations in the cost of materials and so on. Chaos is studied mainly under two different approaches - the nature of the onset of chaos and the statistical description of the chaotic state.

Constraint satisfaction techniques under uncertain conditions for fault diagnosis in nonlinear dynamic systems

The speed of fault isolation is crucial for the design and reconfiguration of fault tolerant control (FTC). In this paper the fault isolation problem is stated as a constraint satisfaction problem (CSP) and solved using constraint propagation techniques. The proposed method is based on constraint satisfaction techniques and uncertainty space refining of interval parameters. In comparison with other approaches based on adaptive observers, the major advantage of the presented method is that the isolation speed is fast even taking into account uncertainty in parameters, measurements and model errors and without the monotonicity assumption. In order to illustrate the proposed approach, a case study of a nonlinear dynamic system is presented

Fault diagnosis by refining the parameter uncertainty space of nonlinear dynamic systems

This paper deals with fault detection and isolation problems for nonlinear dynamic systems. Both problems are stated as constraint satisfaction problems (CSP) and solved using consistency techniques. The main contribution is the isolation method based on consistency techniques and uncertainty space refining of interval parameters. The major advantage of this method is that the isolation speed is fast even taking into account uncertainty in parameters, measurements, and model errors. Interval calculations bring independence from the assumption of monotony considered by several approaches for fault isolation which are based on observers. An application to a well known alcoholic fermentation process model is presented

W3233 -- Networks and Complexity in Social Systems (Collective Dynamics Group ISERP -- Columbia University) Course Syllabus

The Networks and Complexity in Social Systems course commences with an overview of the nascent field of complex networks, dividing it into three related but distinct strands: Statistical description of large scale networks, viewed as static objects; the dynamic evolution of networks, where now the structure of the network is understood in terms of a growth process; and dynamical processes that take place on fixed networks; that is, "networked dynamical systems". (A fourth area of potential research ties all the previous three strands together under the rubric of co-evolution of networks and dynamics, but very little research has been done in this vein and so it is omitted.) The remainder of the course treats each of the three strands in greater detail, introducing technical knowledge as required, summarizing the research papers that have introduced the principal ideas, and pointing out directions for future development. With regard to networked dynamical systems, the course treats in detail the more specific topic of information propagation in networks, in part because this topic is of great relevance to social science, and in part because it has received the most attention in the literature to date.

Assessing the performance of dynamical trajectory estimates

Estimating trajectories and parameters of dynamical systems from observations is a problem frequently encountered in various branches of science; geophysicists for example refer to this problem as data assimilation. Unlike as in estimation problems with exchangeable observations, in data assimilation the observations cannot easily be divided into separate sets for estimation and validation; this creates serious problems, since simply using the same observations for estimation and validation might result in overly optimistic performance assessments. To circumvent this problem, a result is presented which allows us to estimate this optimism, thus allowing for a more realistic performance assessment in data assimilation. The presented approach becomes particularly simple for data assimilation methods employing a linear error feedback (such as synchronization schemes, nudging, incremental 3DVAR and 4DVar, and various Kalman filter approaches). Numerical examples considering a high gain observer confirm the theory.

Bubbling transition to spatial mode excitation in an extended dynamical system

We investigated the transition to spatio-temporal chaos in spatially extended nonlinear dynamical systems possessing an invariant subspace with a low-dimensional attractor. When the latter is chaotic and the subspace is transversely stable we have a spatially homogeneous state only. The onset of spatio-temporal chaos, i.e. the excitation of spatially inhomogeneous modes, occur through the loss of transversal stability of some unstable periodic orbit embedded in the chaotic attractor lying in the invariant subspace. This is a bubbling transition, since there is a switching between spatially homogeneous and nonhomogeneous states with statistical properties of on-off intermittency. Hence the onset of spatio-temporal chaos depends critically both on the existence of a chaotic attractor in the invariant subspace and its being transversely stable or unstable. (C) 2008 Elsevier B.V. All rights reserved.

STABILITY ANALYSIS WITH APPLICATIONS OF A TWO-DIMENSIONAL DYNAMICAL SYSTEM ARISING FROM A STOCHASTIC MODEL FOR AN ASSET MARKET

We analyze the stability properties of equilibrium solutions and periodicity of orbits in a two-dimensional dynamical system whose orbits mimic the evolution of the price of an asset and the excess demand for that asset. The construction of the system is grounded upon a heterogeneous interacting agent model for a single risky asset market. An advantage of this construction procedure is that the resulting dynamical system becomes a macroscopic market model which mirrors the market quantities and qualities that would typically be taken into account solely at the microscopic level of modeling. The system`s parameters correspond to: (a) the proportion of speculators in a market; (b) the traders` speculative trend; (c) the degree of heterogeneity of idiosyncratic evaluations of the market agents with respect to the asset`s fundamental value; and (d) the strength of the feedback of the population excess demand on the asset price update increment. This correspondence allows us to employ our results in order to infer plausible causes for the emergence of price and demand fluctuations in a real asset market. The employment of dynamical systems for studying evolution of stochastic models of socio-economic phenomena is quite usual in the area of heterogeneous interacting agent models. However, in the vast majority of the cases present in the literature, these dynamical systems are one-dimensional. Our work is among the few in the area that construct and study analytically a two-dimensional dynamical system and apply it for explanation of socio-economic phenomena.

Paper surfaces and dynamical limits

It is very common in mathematics to construct surfaces by identifying the sides of a polygon together in pairs: For example, identifying opposite sides of a square yields a torus. In this article the construction is considered in the case where infinitely many pairs of segments around the boundary of the polygon are identified. The topological, metric, and complex structures of the resulting surfaces are discussed: In particular, a condition is given under which the surface has a global complex structure (i.e., is a Riemann surface). In this case, a modulus of continuity for a uniformizing map is given. The motivation for considering this construction comes from dynamical systems theory: If the modulus of continuity is uniform across a family of such constructions, each with an iteration defined on it, then it is possible to take limits in the family and hence to complete it. Such an application is briefly discussed.

PERIODIC PERTURBATION of QUADRATIC SYSTEMS WITH TWO INFINITE HETEROCLINIC CYCLES

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Generic Bifurcations of Planar Filippov Systems via Geometric Singular Perturbations

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)