On the Induction Operation for Shift Subspaces and Cellular Automata as Presentations of Dynamical Systems
Abstract
Description
We consider continuous, translation-commuting transformations of compact, translation-invariant families of mappingsfrom finitely generated groups into finite alphabets. It is well-known that such transformations and spaces can be described "locally" via families of patterns and finitary functions; such descriptions can be re-used on groups larger than the original, usually defining non-isomorphic structures. We show how some of the properties of the "induced" entities can be deduced from those of the original ones, and vice versa; then, we show how to "simulate" the smaller structure into the larger one, and obtain a characterization in terms of group actions for the dynamical systems admitting of presentations via structures as such. Special attention is given to the class of sofic shifts.
20 pages, no figures. Presented at LATA 2008. Extended version, submitted to Information and Computation
20 pages, no figures. Presented at LATA 2008. Extended version, submitted to Information and Computation