archives

Compression Depth and the Behavior of Cellular Automata


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Lathrop, James I. (1996) Compression Depth and the Behavior of Cellular Automata. Technical Report TR96-05, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

A computable complexity measure analogous to computational depth is
developed using the Lempel-Ziv compression algorithm.  This complexity
measure, which we call compression depth, is then applied to the
computational output of cellular automata. We find that compression
depth captures the complexity found in Wolfram Class III celluar
automata, and is in good agreement with his classification scheme.  We
further investigate the rule space of cellular automata using
Langton's Lambda parameter.

Subjects:All uncategorized technical reports
ID code:00000127
Deposited by:Staff Account on 31 May 1996



Contact site administrator at: ssg@cs.iastate.edu