An algebraic measure of complexity
Article

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

Discrete dynamical systems are defined as a set S of states provided with an evolution operator U: S → S; evolution proceeds in discrete time steps. A reading operator σ acting on S that generates a group (σ), is introduced and determines what are the state aspects that are observable. State configurations are thus defined as sets of states that cannot be resolved by σ. The set of configurations is ordered in complexity layers, defined as classes of configurations that are stabilized by isomorphic subgroups of (σ). Layers are indexed by the quotient (σ)/H, where H⊂(σ), up to an isomorphism, stabilizes the configurations in a given layer. Generally, the algebraic complexity is defined as (σ)/H, while for a finite (σ) a complexity number, κσ(x)=[(σ):Gx], is defined, where x ε{lunate} S, and Gx⊂(σ) stabilizes x. Irreversibility of evolution implies that Gx⊂GU.x or, for finite (σ), Δκσ≥0, at every time step in evolution, provided that [σ, U] = 0. This effect of complexity degredation gives the dynamical system the property of selfsimilarity. Translation complexity is used to study onedimensional cellular automata. © 1991.
publication date
funding provided via
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue