Vol. 9, No. 4, 2016

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

Volume 13
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

Volume 12, 8 issues

Volume 11, 5 issues

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
About the Journal
Editorial Board
Editors’ Interests
Subscriptions
 
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Author Index
Coming Soon
 
Other MSP Journals
This article is available for purchase or by subscription. See below.
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.

PDF Access Denied

However, your active subscription may be available on Project Euclid at
https://projecteuclid.org/involve

We have not been able to recognize your IP address 34.232.51.240 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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