Optimal Description of Automatic Paperfolding Sequences
Дата
Авторы
Cerny,Anton
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
paperfolding sequence , automatic sequence , uniform tag system