Automatic Sequences and Zip-Specifications

Details Automatic Sequences and Zip-Specifications Automatic Sequences and Zip-Specifications

2012-01-16

arxiv.org/abs/1201.3251v2

Computer Science

Logic in Computer Science

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Automatic Sequences and Zip-Specifications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Automatic Sequences and Zip-Specifications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic Sequences and Zip-Specifications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-410099