Opacity complexity of automatic sequences. The general case
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913323432280064 |
|---|---|
| author | Allouche, J. -P. Yao, J. -Y. |
| author_facet | Allouche, J. -P. Yao, J. -Y. |
| contents | In this work we introduce a new notion called opacity complexity to measure the complexity of automatic sequences. We study basic properties of this notion, and exhibit an algorithm to compute it. As applications, we compute the opacity complexity of some well-known automatic sequences, including in particular constant sequences, purely periodic sequences, the Thue-Morse sequence, the period-doubling sequence, the Golay-Shapiro(-Rudin) sequence, the paperfolding sequence, the Baum-Sweet sequence, the Tower of Hanoi sequence, and so on. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_13601 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Opacity complexity of automatic sequences. The general case Allouche, J. -P. Yao, J. -Y. Formal Languages and Automata Theory Combinatorics Number Theory 94A17, 68Q45, 11B85 In this work we introduce a new notion called opacity complexity to measure the complexity of automatic sequences. We study basic properties of this notion, and exhibit an algorithm to compute it. As applications, we compute the opacity complexity of some well-known automatic sequences, including in particular constant sequences, purely periodic sequences, the Thue-Morse sequence, the period-doubling sequence, the Golay-Shapiro(-Rudin) sequence, the paperfolding sequence, the Baum-Sweet sequence, the Tower of Hanoi sequence, and so on. |
| title | Opacity complexity of automatic sequences. The general case |
| topic | Formal Languages and Automata Theory Combinatorics Number Theory 94A17, 68Q45, 11B85 |
| url | https://arxiv.org/abs/2404.13601 |