Opacity complexity of automatic sequences. The general case

Jean‐Paul Allouche, Jianhua Yao

Type: Preprint

Publication Date: 2024-04-21

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2404.13601

Abstract

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.

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	On the $N$th linear complexity of automatic sequences	2017	László Mérai Arne Winterhof
+	On the $N$th linear complexity of automatic sequences	2017	László Mérai Arne Winterhof
+	On the Nth linear complexity of automatic sequences	2017	László Mérai Arne Winterhof
+	On the additive complexity of a Thue–Morse-like sequence	2019	Jin Chen Zhi‐Xiong Wen Wen Wu
+	A Survey on Hahn Sequence Space	2013	Murat Ki̇ri̇şçi̇
+ PDF Chat	A new approach to the 2-regularity of the -abelian complexity of 2-automatic sequences	2015	Aline Parreau Michel Rigo Eric Rowland Élise Vandomme
+	Sequences with a Characteristic Number	1971	Irving Adler
+	The distribution of elements in automatic double sequences	2005	Yossi Moshe
+	On Factor Complexity of Morphic Sequences	2018	Rostislav Devyatov
+	A Study on Periodic Sequences	1972	謝清俊 Chieh-Yu Hsieh
+	Barker sequences theory and applications	2009	Kenneth Macdonald
+	Number of Carleson sequences	1981	Vasily Vasyunin
+	The Complexity of Generalized Sturmian Sequences	1996	Shin-ichi Yasutomi
+	Spectral study of automatic and substitutive sequences	1995	Martine Queffélec
+ PDF Chat	A New Approach to the 2-Regularity of the $\ell$-Abelian Complexity of 2-Automatic Sequences	2015	Aline Parreau Michel Rigo Eric Rowland Élise Vandomme
+	THE ALGEBRA OF PERIODIC SEQUENCES	1963	Robert C. Titsworth
+	A new approach to the $2$-regularity of the $\ell$-abelian complexity of $2$-automatic sequences	2014	Aline Parreau Michel Rigo Eric Rowland Élise Vandomme
+	Statistical characteristics of the complexity for prime-periodic sequences	2005	Zhihua Niu LI Nai-cheng Xiao Guo-zhen
+ PDF Chat	Classes of periodic sequences	1958	N. J. Fine
+	ハウスドルフ次元とエントロピー(Fourier Analysis on Arithmetical Sequences)	1983	良和馬場

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors