Optimal Description of Automatic Paperfolding Sequences S=f014578912.pdf

Optimal description of automatic paperfolding sequences Anton Cerny (Kuwait University cerny@math-1.sci.kuniv.edu.kw) Abstract: The class of 2-automatic paperfolding sequences corresponds to the class of ultimately periodic sequences of unfolding instructions. We rst show that a paper- folding sequence is automatic i it is 2-automatic. Then we provide families of minimal nite-state automata, minimal uniform tag sequences and minimal substitutions de- scribing automatic paperfolding sequences, as well as a family of algebraic equations satised by automatic paperfolding sequences understood as formal power series. Key Words: paperfolding sequence, automatic sequence, uniform tag system Category: F.m, F 4.2, G 2.1 1 Introduction Paperfolding sequences are patterns - sequences of folding edges (\peaks and \valleys) - obtained by stepwise folding a stripe of paper. The stripe is always folded in its middle while its initial left-hand side part is kept in a xed position. There are two dierent folding instructions possible: \up { counterclockwise, and \down { clockwise. The result of stepwise folding a stripe of paper following the sequence of instructions up, down, down, as well as the pattern appearing on the unfolded stripe after each step, are depicted in Figure 1. The folding edges are denoted by black points, the xed end of the stripe by a circle, the valleys are denoted by 0, the peaks by 1. The length of the folded stripe is not depicted proportionally. rc  rrc c  $ %  rrrrr r r cXXXXXXXr 0 c r rHHHH r 1 1 0 c r r @ @r r r @ @r r 1 1 0 0 1 0 0 Figure 1: Figure 1: Folding up, down, and down Journal of Universal Computer Science, vol. 3, no. 10 (1997), 1085-1099 submitted: 30/3/97, accepted: 23/9/97, appeared: 28/10/97 ? Springer Pub. Co. If we have two nite sequences of folding instructions, the rst being a sux of the second, then the rst resulting pattern is a prex of the second one. Therefore the folding instruc