Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 3 / Issue 10

available in:   PDF (271 kB) PS (84 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-003-10-1085


Optimal Description of Automatic Paperfolding Sequences

Anton Cerny (Kuwait University, Kuwait)

Abstract: The class of 2-automatic paperfolding sequences corresponds to the class of ultimately periodic sequences of unfolding instructions. We first show that a paper-folding sequence is automatic iff it is 2-automatic. Then we provide families of minimal finite-state automata, minimal uniform tag sequences and minimal substitutions describing automatic paperfolding sequences, as well as a family of algebraic equations satisfied by automatic paperfolding sequences understood as formal power series.

Keywords: automatic sequence, paperfolding sequence, uniform tag system

Categories: F.4.2, F.m, G.2.1