146号初等元胞自动机的演化语言的复杂性

Symbolic dynamics of cellular automata is introduced by coarse-graining the temporal evolution orbits. Evolution languages are defined. By using the theory of formal languages and automata, the complexity of evolution languages of the elementary cellular automaton of rule 146 is studied and it is proved that its width 1-evolution language is regular, but for every n ≥ 2 its width n-evolution language is not context-free but context-sensitive. Also, the same results hold for the equivalent （under conjugation） elementary cellular automaton of rule 182.     

Advances in the study of elementary cellular automata regular language complexity

Cellular automata (CA) are discrete dynamical systems that, out of the fully local action of its state transition rule, are capable of generating a multitude of global patterns, from the trivial to the arbitrarily complex ones. The set of global configurations that can be obtained by iterating a one‐dimensional cellular automaton for a finite number of times can always be described by a regular language. The size of the minimum finite automaton corresponding to such a language at a given time step provides a complexity measure of the underlying rule. Here, we study the time evolution of elementary CA, in terms of such a regular language complexity. We review and expand the original results on the topic, describe an alternative method for generating the subsequent finite automata in time, and provide a method to analyze and detect patterns in the complexity growth of the rules. © 2015 Wiley Periodicals, Inc. Complexity 21: 267–279, 2016     

22号初等元胞自动机的演化复杂性

Cellular automata are the discrete dynamical systems of simple construction but with complex and varied behaviors. In this paper, the elementary cellular automaton of rule 22 is studied by the tools of formal language theory and symbolic dynamics. Its temporal evolution orbits are coarse-grained into evolution sequences and the evolution languages are defined. It is proved that for every n≥2 its width n evolution language is not regular.     

Hybrid one-dimensional reversible cellular automata are regular

It is shown that the set of hybrid one-dimensional reversible cellular automata (CA) with the periodic boundary condition is a regular set. This has several important consequences. For example, it allows checking whether a given CA is reversible and the random generation of a reversible CA from the uniform distribution, both using time polynomial in the size of the CA. Unfortunately, the constant term in the resulting random generation algorithm is much too large to be of practical use. We show that for the less general case of null boundary (NB) CA, this constant can be reduced drastically, hence facilitating a practical algorithm for uniform random generation. Our techniques are further applied asymptotically to count the number of reversible NBCA.     

22号初等元胞自动机的极限语言复杂性

§1Introduction Thetaskofthispaperistosolvetheproblemproposedin[1],i.e.,toexplorethe complexityoflimitset,orequivalently,limitlanguageoftheelementarycellularautomaton ofrule22bythetoolsofformallanguagetheory.Cellularautomata(abbreviatedasCA),asmathematicalmodelsforcomplexnatural systemscontaininglargenumbersofsimpleidenticalcomponentswithlocalinteractions,havebeenwidelyusedinphysical,biological,chemicalandcomputationalsystems[2].Despitetheirsimpleconstruction,someCAcandisplayveryrichandcompl…     

Prevalence of odometers in cellular automata

We consider left permutive cellular automata  with no memory and positive anticipation, defined on the space of all doubly infinite sequences with entries from a finite alphabet. For each such automaton that is not one-to-one, there is a dense set of points  such that is topologically conjugate to an odometer, the ``' map on the countable product of finite cyclic groups. This set is a dense subset of an appropriate subspace. We identify the odometer in several cases.

     

Flexible toggles and symmetric invertible asynchronous elementary cellular automata

A sequential dynamical system (SDS) consists of a graph $G$ with vertices $v_1,\dots ,v_n$, a state set $A$, a collection of “vertex functions” ${\left\{f_{v_i}\right\}}_{i=1}^n$, and a permutation $\pi \in S_n$ that specifies how to compose these functions to yield the SDS map $[G,{\left\{f_{v_i}\right\}}_{i=1}^n,\pi ]:A^n\to A^n$. In this paper, we study symmetric invertible SDS defined over the cycle graph $C_n$ using the set of states ${\mathbb{F}}_2$. These are, in other words, asynchronous elementary cellular automata (ECA) defined using ECA rules 150 and 105. Each of these SDS defines a group action on the set ${\mathbb{F}}_2^n$ of $n$-bit binary vectors. Because the SDS maps are products of involutions, this relates to generalized toggle groups, which Striker recently introduced. In this paper, we further generalize the notion of a generalized toggle group to that of a flexible toggle group; the SDS maps we consider are examples of Coxeter elements of flexible toggle groups.Our main result is the complete classification of the dynamics of symmetric invertible SDS defined over cycle graphs using the set of states ${\mathbb{F}}_2$ and the identity update order $\pi =123?n$. More precisely, if $T$ denotes the SDS map of such an SDS, then we obtain an explicit formula for $\left|{\text{Per}}_r\left(T\right)\right|$, the number of periodic points of $T$ of period $r$, for every positive integer $r$. It turns out that if we fix $r$ and vary $n$ and $T$, then $\left|{\text{Per}}_r\left(T\right)\right|$ only takes at most three nonzero values.     

The emergence of dynamical complexity: An exploration using elementary cellular automata

This work concerns the interaction between two classical problems: the forecasting of the dynamical behaviors of elementary cellular automata (ECA) from its intrinsic mathematical laws and the conditions that determine the emergence of complex dynamics. To approach these problems, and inspired by the theory of reversible logical gates, we decompose the ECA laws in a “spectrum” of dyadic Boolean gates. Emergent properties due to interactions are captured generating another spectrum of logical gates. The combined analysis of both spectra shows the existence of characteristic bias in the distribution of Boolean gates for ECA belonging to different dynamical classes. These results suggest the existence of signatures capable to indicate the propensity to develop complex dynamics. Logical gates “exclusive‐or” and “equivalence” are among these signatures of complexity. An important conclusion is that within ECA space, interactions are not capable to generate signatures of complexity in the case these signatures are absent in the intrinsic law of the automaton. © 2004 Wiley Periodicals, Inc. Complexity 9: 33–42, 2004     

Latent class models for time series analysis

Latent class analysis of time series designed to classify and compare sets of series is discussed. For a particular time series in latent class the data are independently normally distributed with a vector of means, and common variance , that is, . The function of time, , can be represented by a linear combination of low-order splines (piecewise polynomials). The probability density function for the data of a time series is posited to be a finite mixture of spherical multivariate normal densities. The maximum-likelihood function is optimized by means of an EM algorithm. The stability of the estimates is investigated using a bootstrap procedure. Examples of real and artificial data are presented. Copyright © 1999 John Wiley & Sons, Ltd.     

Multiscaling comparative analysis of time series and geophysical phenomena

Different methods are used to determine the scaling exponents associated with a time series describing a complex dynamical process, such as those observed in geophysical systems. Many of these methods are based on the numerical evaluation of the variance of a diffusion process whose step increments are generated by the data. An alternative method focuses on the direct evaluation of the scaling coefficient of the Shannon entropy of the same diffusion distribution. The combined use of these methods can efficiently distinguish between fractal Gaussian and Lévy‐walk time series and help to discern between alternative underling complex dynamics. © 2005 Wiley Periodicals, Inc. Complexity 10: 51–56, 2005     

A note on the time series which is the product of two stationary time series

The time series […,x_-1y_-1,x₀y₀,x₁y₁,…]> which is the product of two stationary time series x_t and y_t is studied. Such sequences arise in the study of nonlinear time series, censored time series, amplitude modulated time series, time series with random parameters, and time series with missing observations. The mean and autocovariance function of the product sequence are derived.     

Topological analysis of chaotic time series data from the Belousov-Zhabotinskii reaction

Summary We have applied topological methods to analyze chaotic time series data from the Belousov-Zhabotinskii reaction. First, the periodic orbits shadowed by the data set were identified. Next, a three-dimensional embedding without self-intersections was constructed from the data set. The topological structure of that flow was visualized by constructing a branched manifold such that every periodic orbit in the flow could be held by the branched manifold. The branched manifold, or induced template, was computed using the three lowest-period orbits. The organization of the higher-period orbits predicted by this induced template was compared with the organization of the orbits reconstructed from the data set with excellent results. The consequences of the presence of certain knots found in the data are discussed.     

How to make dull cellular automata complex by adding memory: Rule 126 case study

Using Rule 126 elementary cellular automaton (ECA), we demonstrate that a chaotic discrete system — when enriched with memory — hence exhibits complex dynamics where such space exploits on an ample universe of periodic patterns induced from original information of the ahistorical system. First, we analyze classic ECA Rule 126 to identify basic characteristics with mean field theory, basins, and de Bruijn diagrams. To derive this complex dynamics, we use a kind of memory on Rule 126; from here interactions between gliders are studied for detecting stationary patterns, glider guns, and simulating specific simple computable functions produced by glider collisions. © 2010 Wiley Periodicals, Inc. Complexity, 2010     

Multivariate time series analysis

Some key theorems in the asymptotic theory for multivariate time series, using spectrl methods, are established. These theorems relate to various estimation situations including multiple systems of regressions, the determination of the frequency of a periodic signal and the determination of the velocity of a signal propagated through a dispersive medium and received with noise at a number of recorders. The theorems are of a general kind and relate to the almost sure convergence of averages of the periodogram and to the limiting covariance properties and the central limit theorem for such averages. Some brief indications are given concerning extensions of the results to cases where processes are observed that are stationary in time and homogenous with respect to spatial translation.     

Stock market forecasting by using a hybrid model of exponential fuzzy time series

The initial aim of this study is to propose a hybrid method based on exponential fuzzy time series and learning automata based optimization for stock market forecasting. For doing so, a two-phase approach is introduced. In the first phase, the optimal lengths of intervals are obtained by applying a conventional fuzzy time series together with learning automata swarm intelligence algorithm to tune the length of intervals properly. Subsequently, the obtained optimal lengths are applied to generate a new fuzzy time series, proposed in this study, named exponential fuzzy time series. In this final phase, due to the nature of exponential fuzzy time series, another round of optimization is required to estimate certain method parameters. Finally, this model is used for future forecasts. In order to validate the proposed hybrid method, forty-six case studies from five stock index databases are employed and the findings are compared with well-known fuzzy time series models and classic methods for time series. The proposed model has outperformed its counterparts in terms of accuracy.     

Emergence of density dynamics by surface interpolation in elementary cellular automata

A classic problem in elementary cellular automata (ECAs) is the specification of numerical tools to represent and study their dynamical behaviour. Mean field theory and basins of attraction have been commonly used; however, although the first case gives the long term estimation of density, frequently it does not show an adequate approximation for the step-by-step temporal behaviour; mainly for non-trivial behaviour. In the second case, basins of attraction display a complete representation of the evolution of an ECA, but they are limited up to configurations of 32 cells; and for the same ECA, one can obtain tens of basins to analyse. This paper is devoted to represent the dynamics of density in ECAs for hundreds of cells using only two surfaces calculated by the nearest-neighbour interpolation. A diversity of surfaces emerges in this analysis. Consequently, we propose a surface and histogram based classification for periodic, chaotic and complex ECA.     

Prediction of multivariate time series by autoregressive model fitting

Suppose the stationary r-dimensional multivariate time series {y_t} is generated by an infinite autoregression. For lead times h≥1, the linear prediction of y_t+h based on y_t, y_t−1,… is considered using an autoregressive model of finite order k fitted to a realization of length T. Assuming that k → ∞ (at some rate) as T → ∞, the consistency and asymptotic normality of the estimated autoregressive coefficients are derived, and an asymptotic approximation to the mean square prediction error based on this autoregressive model fitting approach is obtained. The asymptotic effect of estimating autoregressive parameters is found to inflate the minimum mean square prediction error by a factor of (1 + kr/T).     

Guidelines for dynamics‐based parameterization of one‐dimensional cellular automata rule spaces

As paradigmatic complex systems, various studies have been done in the context of one‐dimensional cellular automata (CA) on the definition of parameters directly obtained from their transition rule, aiming at the help they might provide to forecasting CA dynamic behavior. Out of the analysis of the most important parameters available for this end, as well as others evaluated by us, a set of guidelines is proposed that should be followed when defining a parameter of that kind. Based upon the guidelines, a critique of those parameters is made, which leads to a set of five that jointly provide a good forecasting set; two of them were drawn from the literature and three are new ones defined according to the guidelines. By using them as a heuristic in the evolutionary search for CA of a predefined computational behavior, good results have been obtained, exemplified herein by the evolutionary search for CA that perform the Synchronization Task. © 2001 John Wiley & Sons, Inc.     

基于时间序列分析的北京地区PM2.5浓度研究

基于中国环境监测总站公布的实时空气质量监测数据, 利用时间序列模型对PM2.5指标的数据进行了平稳性、纯随机性检验, 同时进行了模型阶数、未知参数估计以及模型显著性检验与优化. 最终在此基础上建立了指标预测的数学模型, 并对未来三天的PM2.5浓度值进行预测. 进一步地, 基于向量自回归(VAR)模型, 对北京市万寿西宫站PM2.5数据进行相关性分析, 研究空气中污染物O_{2}、NO_{2}、CO、O_{3}、PM10与PM2.5的动态影响关系. 研究发现当天的PM2.5浓度会受到前几天PM2.5、PM10、O_{3}、SO_{2}等污染物浓度的影响,其中PM10对PM2.5的影响最为明显且持续时间最长, O_{3}、SO_{2}对PM2.5浓度的影响在二、三期最为明显.     

Canonical correlation and reduction of multiple time series

It is shown that a degenerate rankd-variate stationary time series can be reduced to a full rank time series of lower dimension via an orthogonal transformationT provided that , the canonical correlation between past and future of the time series is strictly less than one. Procedures for estimation of rank of the multiple time series,T and testing =1 are outlined, the latter is related to testing the unit root hypothesis in ARMA models.