Local causal states and discrete coherent structures

Algebraic Theory of Patterns as Generalized Symmetries

We generalize the exact predictive regularity of symmetry groups to give an algebraic theory of patterns, building from a core principle of future equivalence. For topological patterns in fully-discrete one-dimensional systems, future equivalence uniquely specifies a minimal semiautomaton. We demonstrate how the latter and its semigroup algebra generalizes translation symmetry to partial and hidden symmetries. This generalization is not as straightforward as previously considered. Here, though, we clarify the underlying challenges. A stochastic form of future equivalence, known as predictive equivalence, captures distinct statistical patterns supported on topological patterns. Finally, we show how local versions of future equivalence can be used to capture patterns in spacetime. As common when moving to higher dimensions, there is not a unique local approach, and we detail two local representations that capture different aspects of spacetime patterns. A previously developed local spacetime variant of future equivalence captures patterns as generalized symmetries in higher dimensions, but we show that this representation is not a faithful generator of its spacetime patterns. This motivates us to introduce a local representation that is a faithful generator, but we demonstrate that it no longer captures generalized spacetime symmetries. Taken altogether, building on future equivalence, the theory defines and quantifies patterns present in a wide range of classical field theories.

Discovering causal structure with reproducing-kernel Hilbert space ε-machines

We merge computational mechanics' definition of causal states (predictively equivalent histories) with reproducing-kernel Hilbert space (RKHS) representation inference. The result is a widely applicable method that infers causal structure directly from observations of a system's behaviors whether they are over discrete or continuous events or time. A structural representation-a finite- or infinite-state kernel ϵ-machine-is extracted by a reduced-dimension transform that gives an efficient representation of causal states and their topology. In this way, the system dynamics are represented by a stochastic (ordinary or partial) differential equation that acts on causal states. We introduce an algorithm to estimate the associated evolution operator. Paralleling the Fokker-Planck equation, it efficiently evolves causal-state distributions and makes predictions in the original data space via an RKHS functional mapping. We demonstrate these techniques, together with their predictive abilities, on discrete-time, discrete-value infinite Markov-order processes generated by finite-state hidden Markov models with (i) finite or (ii) uncountably infinite causal states and (iii) continuous-time, continuous-value processes generated by thermally driven chaotic flows. The method robustly estimates causal structure in the presence of varying external and measurement noise levels and for very high-dimensional data.

Shift-symmetric configurations in two-dimensional cellular automata: Irreversibility, insolvability, and enumeration

The search for symmetry, as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have long been a central focus of complexity science and physics. To better grasp and understand symmetry of configurations in decentralized toroidal architectures, we employ group-theoretic methods, which allow us to identify and enumerate these inputs, and argue about irreversible system behaviors with undesired effects on many computational problems. The concept of so-called "configuration shift-symmetry" is applied to two-dimensional cellular automata as an ideal model of computation. Regardless of the transition function, the results show the universal insolvability of crucial distributed tasks, such as leader election, pattern recognition, hashing, and encryption. By using compact enumeration formulas and bounding the number of shift-symmetric configurations for a given lattice size, we efficiently calculate the probability of a configuration being shift-symmetric for a uniform or density-uniform distribution. Further, we devise an algorithm detecting the presence of shift-symmetry in a configuration. Given the resource constraints, the enumeration and probability formulas can directly help to lower the minimal expected error and provide recommendations for system's size and initialization. Besides cellular automata, the shift-symmetry analysis can be used to study the nonlinear behavior in various synchronous rule-based systems that include inference engines, Boolean networks, neural networks, and systolic arrays.

Introduction to Focus Issue: Causation inference and information flow in dynamical systems: Theory and applications

Questions of causation are foundational across science and often relate further to problems of control, policy decisions, and forecasts. In nonlinear dynamics and complex systems science, causation inference and information flow are closely related concepts, whereby "information" or knowledge of certain states can be thought of as coupling influence onto the future states of other processes in a complex system. While causation inference and information flow are by now classical topics, incorporating methods from statistics and time series analysis, information theory, dynamical systems, and statistical mechanics, to name a few, there remain important advancements in continuing to strengthen the theory, and pushing the context of applications, especially with the ever-increasing abundance of data collected across many fields and systems. This Focus Issue considers different aspects of these questions, both in terms of founding theory and several topical applications.