Semiperiodic words and root-conjugacy

A factor u of a word w is called right special if there exist two distinct letters a and b such that both ua and ub are factors of w. Left special factors are defined symmetrically. By R w (resp. L w ) we denote the minimal natural number such that there is no right (resp. left) special factor of w...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2003-01, Vol.292 (1), p.111-130
Main Authors: Carpi, Arturo, Luca, Aldo de
Format: Article
Language:English
Subjects:
Algebra
Boxes
Combinatorics. Ordered structures
Exact sciences and technology
General algebraic systems
Group theory
Group theory and generalizations
Logic and foundations
Mathematical logic, foundations, set theory
Mathematics
Order, lattices, ordered algebraic structures
Recursion theory
Root-conjugacy
Sciences and techniques of general use
Semiperiodic words
Special factors
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:A factor u of a word w is called right special if there exist two distinct letters a and b such that both ua and ub are factors of w. Left special factors are defined symmetrically. By R w (resp. L w ) we denote the minimal natural number such that there is no right (resp. left) special factor of w of length R w (resp. L w ). Moreover, H w (resp. K w ) denotes the length of the shortest prefix (resp. suffix) which cannot be extended on the left (resp. right) in w. The parameters R w, L w, H w, and K w give interesting information on the structure of the word w. We consider the class of all finite words w such that R w
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(01)00218-3