On the computational complexity of the Arnold complexity of binary words

DOI10.1142/S1793557109000546MaRDI QIDQ5189966zbMATH OpenOpenAlexFDO

Authors Yuri Vladimirovich Merekin

Publication date 11 March 2010

Published in Asian-European Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793557109000546

zbMATH Keywords

binary wordcomplexity of wordscomputational complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• On the computation of Arnold complexity of length \(2^{n}\) binary words
• The Shannon function for calculating the Arnold complexity of length 2 n binary words
• scientific article; zbMATH DE number 6466091
• Computing abelian complexity of binary uniform morphic words
• Automata calculating the complexity of automatic sequences

Cites work

• Complexity of sequences and dynamical systems
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• On addition chains

Cited in

(5)

• Arithmetical complexity of symmetric D0L words.
• On the computation of Arnold complexity of length \(2^{n}\) binary words
• The Shannon function for calculating the Arnold complexity of length 2 n binary words
• scientific article; zbMATH DE number 6466091 (Why is no real title available?)
• A new estimate on complexity of binary generalized pseudostandard words

This page was built for publication: On the computational complexity of the Arnold complexity of binary words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5189966)