Complexity of Rule-Dynamical Systems

摘要

It is known that CA map preserves trios. In other words, finite number of iterations of the CA map cannot take us to a higher (lower) level in Chomsky hierarchy. This means that a regular language is always mapped to a regular language, and a context-free language is always mapped to a context-free language, and so on. The main results described previous section suggest that rule-dynamical map does not preserve trios. This is the crucial difference between CA and RD.