Vol. 9, No. 4, 2016

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11, 1 issue

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Avoiding approximate repetitions with respect to the longest common subsequence distance

Serina Camungol and Narad Rampersad

Vol. 9 (2016), No. 4, 657–666
Abstract

Ochem, Rampersad, and Shallit gave various examples of infinite words avoiding what they called approximate repetitions. An approximate repetition is a factor of the form xx, where x and x are close to being identical. In their work, they measured the similarity of x and x using either the Hamming distance or the edit distance. In this paper, we show the existence of words avoiding approximate repetitions, where the measure of similarity between adjacent factors is based on the length of the longest common subsequence. Our principal technique is the so-called “entropy compression” method, which has its origins in Moser and Tardos’s algorithmic version of the Lovász local lemma.

Keywords
approximate repetition, longest common subsequence, entropy compression
Mathematical Subject Classification 2010
Primary: 68R15
Milestones
Received: 20 March 2015
Revised: 6 September 2015
Accepted: 17 September 2015
Published: 6 July 2016

Communicated by Joshua Cooper
Authors
Serina Camungol
Department of Mathematics and Statistics
University of Winnipeg
515 Portage Ave.
Winnipeg MB R3B 2E9
Canada
Narad Rampersad
Department of Mathematics and Statistics
University of Winnipeg
515 Portage Ave.
Winnipeg MB R3B 2E9
Canada