An algebraic measure of complexity

algebraic complexity algebraic measure of complexity complexity degradation discrete dynamical system one-dimensional cellular automata reading operator set of states translation complexity

Mathematics Subject Classification ID

Topological dynamics (37B99)

Review text

The notion of an algebraic measure of complexity is discussed: Given a discrete dynamical system U: \(S\to S\), where S is the set of states, a reading operator \(\sigma\) acting on S is introduced which determines which state aspects are observable and this generates a group (\(\sigma\)). State configurations are thus defined as sets of states that cannot be resolved by \(\sigma\). The set of configurations is ordered in complexity layers, defined as classes of configurations that are stabilized by isomorphic subgroups of (\(\sigma\)). These layers are indexed by (\(\sigma\))/H where H, up to an isomorphism, stabilizes the configuration of a given layer. The algebraic complexity is given as (\(\sigma\))/H and for finite (\(\sigma\)) a complexity number is introduced. The notions of complexity degradation and translation complexity are discussed with particular reference to one-dimensional cellular automata.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: An algebraic measure of complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640205)