Square-free partial words

We say that a partial word w over an alphabet A is square-free if every factor x x ′ of w such that x and x ′ are compatible is either of the form ⋄ a or a⋄ where ⋄ is a hole and a ∈ A . We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite num...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2008-11, Vol.108 (5), p.290-292
Main Authors: Halava, Vesa, Harju, Tero, Kärki, Tomi
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorial problems
Combinatorics
Computer science
control theory
systems
Exact sciences and technology
Information processing
Leech word
Mathematical functions
Miscellaneous
Partial word
Square-free
Studies
Theoretical computing
Thue–Morse word
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We say that a partial word w over an alphabet A is square-free if every factor x x ′ of w such that x and x ′ are compatible is either of the form ⋄ a or a⋄ where ⋄ is a hole and a ∈ A . We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite number of holes.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2008.06.001