  We consider infinite sequences of symbols, also known as streams, and the
decidability question for equality of streams defined in a restricted format.
This restricted format consists of prefixing a symbol at the head of a stream,
of the stream function `zip', and recursion variables. Here `zip' interleaves
the elements of two streams in alternating order, starting with the first
stream. For example, the Thue-Morse sequence is obtained by the
`zip-specification' {M = 0 : X, X = 1 : zip(X,Y), Y = 0 : zip(Y,X)}. Our
analysis of such systems employs both term rewriting and coalgebraic
techniques. We establish decidability for these zip-specifications, employing
bisimilarity of observation graphs based on a suitably chosen cobasis. The
importance of zip-specifications resides in their intimate connection with
automatic sequences. We establish a new and simple characterization of
automatic sequences. Thus we obtain for the binary zip that a stream is
2-automatic iff its observation graph using the cobasis (hd,even,odd) is
finite. The generalization to zip-k specifications and their relation to
k-automaticity is straightforward. In fact, zip-specifications can be perceived
as a term rewriting syntax for automatic sequences. Our study of
zip-specifications is placed in an even wider perspective by employing the
observation graphs in a dynamic logic setting, leading to an alternative
characterization of automatic sequences. We further obtain a natural extension
of the class of automatic sequences, obtained by `zip-mix' specifications that
use zips of different arities in one specification. We also show that
equivalence is undecidable for a simple extension of the zip-mix format with
projections like even and odd. However, it remains open whether zip-mix
specifications have a decidable equivalence problem.
