Squarefree words with interior disposable factors

DOI10.1016/J.TCS.2021.02.023zbMATH Open1497.68406arXiv2007.03557OpenAlexW3129584233MaRDI QIDQ2658049FDOQ2658049

Authors: Narad Rampersad, Marko Milošević 

Publication date: 18 March 2021

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

Abstract: We give a partial answer to a problem of Harju by constructing an infinite ternary squarefree word $w$ with the property that for every $kgeq3312$ there is an interior length-$k$ factor of $w$ that can be deleted while still preserving squarefreeness. We also examine Thue's famous squarefree word (generated by iterating the map $0o012$, $1o02$, $2o1$) and characterize the positions $i$ for which deleting the symbol appearing at position $i$ preserves squarefreeness.

Full work available at URL: https://arxiv.org/abs/2007.03557

Recommendations

• Disposability in square-free words
• Extremal square-free words
• Squarefree extensions of words
• Finite test sets for morphisms that are squarefree on some of Thue's squarefree ternary words
• scientific article; zbMATH DE number 3894492

zbMATH Keywords

squarefree worddisposabilitysquarefree morphism

Mathematics Subject Classification ID

Combinatorics on words (68R15) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Cites Work

• How many squares must a binary sequence contain?
• Automatic Sequences
• Uniformly growing k-th power-free homomorphisms
• Title not available (Why is that?)
• Extremal square-free words
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unending chess, symbolic dynamics and a problem in semi-groups
• Abelian complexity of fixed point of morphism \(0 \mapsto 012, 1 \mapsto 02, 2 \mapsto 1\)
• Title not available (Why is that?)
• Disposability in square-free words
• The upper density of an automatic set is rational
• Some further results on squarefree arithmetic progressions in infinite words

Cited In (2)

• Disposability in square-free words
• Extensions and reductions of squarefree words

Uses Software

• Walnut

This page was built for publication: Squarefree words with interior disposable factors

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