Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups

DOI10.1016/0304-3975(89)90013-3zbMath0671.10050OpenAlexW1968553864MaRDI QIDQ1119694

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90013-3

zbMATH Keywords

algorithm Thue-Morse sequence enumeration formula special factors of given length Thue-Morse monoid total number of factors weakly permutable monoid

Mathematics Subject Classification ID

Formal languages and automata (68Q45) General structure theory for semigroups (20M10) Sequences and sets (11B99)

Related Items (59)

Canonical positions for the factors in paperfolding sequences ⋮ Pentagonal chains and annuli as models for designing nanostructures from cages ⋮ Automata calculating the complexity of automatic sequences ⋮ Words with the Maximum Number of Abelian Squares ⋮ A Square Root Map on Sturmian Words ⋮ The subword complexity of fixed points of binary uniform morphisms ⋮ A relative of the Thue-Morse sequence ⋮ The subword complexity of polynomial subsequences of the Thue-Morse sequence ⋮ On the context-freeness of the set of words containing overlaps ⋮ The number of factors in a paperfolding sequence ⋮ Pseudorandom sequences derived from automatic sequences ⋮ Renormalization, thermodynamic formalism and quasi-crystals in subshifts ⋮ A combinatorial theorem on $p$-power-free words and an application to semigroups ⋮ Special factors of automatic sequences ⋮ Factorial languages whose growth function is quadratically upper bounded ⋮ On abelian 2-avoidable binary patterns ⋮ Complexity of Toeplitz sequences ⋮ Languages invariant under more symmetries: overlapping factors versus palindromic richness ⋮ Properties of infinite words : Recent results ⋮ Proving results about OEIS sequences with \texttt{Walnut} ⋮ On the structure of compacted subword graphs of Thue-Morse words and their applications ⋮ Möbius orthogonality of the Thue–Morse sequence along Piatetski-Shapiro numbers ⋮ Formulas for complexity, invariant measure and RQA characteristics of the period-doubling subshift ⋮ Resolution of an integral equation with the Thue-Morse sequence ⋮ Palindromic closures using multiple antimorphisms ⋮ A characterization of words of linear complexity ⋮ Normality along squares ⋮ A finiteness condition for semigroups generalizing a theorem of Hotzel ⋮ On $t$-extensions of the Hankel determinants of certain automatic sequences ⋮ Permutation properties with some restrictions. ⋮ Fibonacci morphisms and Sturmian words ⋮ On a combinatorial property of Sturmian words ⋮ Subword complexity of a generalized Thue-Morse word ⋮ On the subword complexity of Thue-Morse polynomial extractions ⋮ On fixed-point-free permutation properties in groups and semigroups ⋮ Cyclic complexity of words ⋮ The ring of $k$-regular sequences ⋮ Permutation complexity of the Thue-Morse word ⋮ Generalized Thue-Morse words and palindromic richness ⋮ Words and special factors ⋮ Pattern avoidance: themes and variations ⋮ Stefano Varricchio (1960-2008) ⋮ Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture ⋮ Computing the $k$-binomial complexity of the Thue-Morse word ⋮ A note on $\omega$-permutable semigroups ⋮ On winning shifts of marked uniform substitutions ⋮ Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns ⋮ Infinite words and permutation properties ⋮ Infinite words with linear subword complexity ⋮ Enumeration of factors in the Thue-Morse word ⋮ WHEN THUE-MORSE MEETS KOCH ⋮ PERMUTATION COMPLEXITY AND THE LETTER DOUBLING MAP ⋮ Subword complexity and power avoidance ⋮ On the combinatorics of finite words ⋮ Expansions of generalized Thue-Morse numbers ⋮ On a combinatorial property of Fibonacci semigroup ⋮ On bispecial factors of the Thue-Morse word ⋮ Words and forbidden factors ⋮ Complexity of generalized Rudin-Shapiro sequences

Cites Work

This page was built for publication: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups