A new estimate on complexity of binary generalized pseudostandard words

MaRDI QIDQ5384198zbMATH OpenFDO

Authors Josef Florian, L'ubomíra Dvořáková

Publication date 21 June 2019

Full work available at URL https://arxiv.org/abs/1611.05482, http://math.colgate.edu/~integers/r61/r61.pdf

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

Abstract: Generalized pseudostandard words were introduced by de Luca and De Luca in 2006. In comparison to the palindromic and pseudopalindromic closure, only little is known about the generalized pseudopalindromic closure and the associated generalized pseudostandard words. We present a counterexample to Conjecture 43 from a paper by Blondin Mass'e et al. that estimated the complexity of binary generalized pseudostandard words as $mathcalC(n)leq4n$ for all sufficiently large $n$. We conjecture that $mathcalC(n)<6n$ for all $ninmathbbN$.

Recommendations

• On generalized pseudostandard words over binary alphabets
• On the computational complexity of the Arnold complexity of binary words
• scientific article; zbMATH DE number 4045148
• On periodicity of generalized pseudostandard words
• On the multiplicative complexity of binary words with a given number of units.
• On the computation of Arnold complexity of length \(2^{n}\) binary words
• scientific article; zbMATH DE number 3954821
• Fixed points of morphisms among binary generalized pseudostandard words
• Fast computation of the Arnold complexity of length \(2^{n}\) binary words
• The subword complexity of a class of infinite binary words

Cites work

• Complexity and special factors
• Episturmian words and some constructions of de Luca and Rauzy
• On generalized pseudostandard words over binary alphabets
• On periodicity of generalized pseudostandard words
• On some problems related to palindrome closure
• On the fixed points of the iterated pseudopalindromic closure operator
• Palindromic closures using multiple antimorphisms
• Pseudopalindrome closure operators in free monoids
• Sturmian words: structure, combinatorics, and their arithmetics
• Symbolic Dynamics

Cited in

(4)

• Normalization of ternary generalized pseudostandard words
• Fixed points of morphisms among binary generalized pseudostandard words
• On generalized pseudostandard words over binary alphabets
• On periodicity of generalized pseudostandard words

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: A new estimate on complexity of binary generalized pseudostandard words

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