  I investigate a class of dynamical systems in which finite pieces of
spacetime contain finite amounts of information. Most of the guiding principles
for designing these systems are drawn from general relativity: the systems are
deterministic; spacetime may be foliated into Cauchy surfaces; the law of
evolution is local (there is a light-cone structure); and the geometry evolves
locally (curvature may be present; big bangs are possible). However, the
systems differ from general relativity in that spacetime is a combinatorial
object, constructed by piecing together copies of finitely many types of
allowed neighborhoods in a prescribed manner. Hence at least initially there is
no metric. The role of diffeomorphism is played by a combinatorial equivalence
map which is local and preserves information content. Most of my results come
in the 1+1-dimensional oriented case. There sets of spaces may be described
equivalently by matrices of nonnegative integers, directed graphs, or symmetric
tensors; local equivalences between space sets are generated by simple matrix
transformations. These equivalence maps turn out to be closely related to the
flow equivalence maps between subshifts of finite type studied in symbolic
dynamics. Also, the symmetric tensor algebra generated by equivalence
transformations turns out to be isomorphic to the abstract tensor algebra
generated by commutative cocommutative bialgebras. In higher dimensions I study
the case where space is a special type of colored graph (discovered by Pezzana)
which may be interpreted as an n-dimensional pseudomanifold. Finally, I show
how one may study the behavior of combinatorial spacetimes by searching for
constants of motion, which typically are associated with local flows and often
may be interpreted in terms of particles.
