Overlap-free words and spectra of matrices

DOI10.1016/j.tcs.2009.04.022zbMath1171.68035OpenAlexW2093900036WikidataQ60692281 ScholiaQ60692281MaRDI QIDQ837157

Raphaël M. Jungers, Blondel, Vincent D., Vladimir Yu. Protasov

Publication date: 10 September 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.022

zbMATH Keywords

joint spectral radiusLyapunov exponentcombinatorics on wordsjoint spectral subradiusoverlap-free words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (18)

Asymptotics of products of nonnegative random matrices ⋮ An experimental study of approximation algorithms for the joint spectral radius ⋮ Lower and upper bounds for the largest Lyapunov exponent of matrices ⋮ The Barabanov Norm is Generically Unique, Simple, and Easily Computed ⋮ Antinorms on cones: duality and applications ⋮ Exact computation of joint spectral characteristics of linear operators ⋮ Rank-one characterization of joint spectral radius of finite matrix family ⋮ On asymptotic properties of matrix semigroups with an invariant cone ⋮ Deciding context equivalence of binary overlap-free words in linear time ⋮ Unnamed Item ⋮ Growth properties of power-free languages ⋮ When do several linear operators share an invariant cone? ⋮ The Number of Threshold Words on $n$ Letters Grows Exponentially for Every $n\geq 27$ ⋮ On the number of \(\alpha \)-power-free binary words for \(2<\alpha \leq 7/3\) ⋮ Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices ⋮ Transition property for cube-free words ⋮ Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution ⋮ Stability of Linear Problems: Joint Spectral Radius of Sets of Matrices

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial versus exponential growth in repetition-free binary words
• Enumeration of irreducible binary words
• Bounded semigroups of matrices
• Overlap-free words and finite automata
• The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate
• On the accuracy of the ellipsoid norm approximation of the joint spectral radius
• An upper bound for the largest Lyapunov exponent of a Markovian product of nonnegative matrices
• Enumeration of factors in the Thue-Morse word
• On the finiteness property for rational matrices
• Efficient algorithms for deciding the type of growth of products of integer matrices
• Approximation of the joint spectral radius using sum of squares
• Growth of repetition-free words -- a review
• On the Complexity of Computing the Capacity of Codes That Avoid Forbidden Difference Patterns
• A linear-time algorithm to decide whether a binary word contains an overlap
• The generalized joint spectral radius. A geometric approach
• Asymptotic behaviour of the partition function
• On the regularity of de Rham curves
• Computationally Efficient Approximations of the Joint Spectral Radius
• A survey of computational complexity results in systems and control

This page was built for publication: Overlap-free words and spectra of matrices