A3 Refereed book chapter or chapter in a compilation book

Minimal Similarity Relations for Square-Free Words




AuthorsT. Harju, T. Kärki

EditorsGh. Paun, G. Rozenberg, A. Salomaa

Publishing placeBucharest

Publication year2014

Book title Discrete Mathematics and Computer Science. In Memoriam Alexandru Mateescu (1952-2005)

First page 193

Last page200

ISBN978-973-27-2470-5


Abstract

A relation R on words is a similarity relation if it is reflexive, symmetric and it is generated by letters. A word w is said to be R-square–free, if it has no factors of the form uv where u and v are related by R. We give a new proof for the result of Kärki [Fund. Inform., 116 (2012)] that the smallest similarity relation that gives an infinite square–free word is generated by six pairs.We also characterize all trees of order six corresponding to the similarity relations that admit a square–free word.




Last updated on 2024-26-11 at 22:13