Grants and Contributions:

Back to search

Title:

Extendibility and growth of words avoiding patterns

Agreement Number:

RGPIN

Agreement Value:

$70,000.00

Agreement Date:

May 10, 2017 -

Organization:

Natural Sciences and Engineering Research Council of Canada

Location:

Manitoba, CA

Reference Number:

GC-2017-Q1-01589

Agreement Type:

Grant

Report Type:

Grants and Contributions

Additional Information:

Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023)

Recipient's Legal Name:

Currie, James (The University of Winnipeg)

Program:

Discovery Grants Program - Individual

Program Purpose:

In the modern world, long sequences of symbols over small alphabets are of basic importance. Whether we are considering streams of 0's and 1's over the internet, or considering long DNA sequences made up from the letters A, C, G, T, understanding the mathematics of strings of symbols is of basic importance. This research studies the regularities and irregularities in long strings of symbols, identifying which patterns must always arise, and which can be avoided. The simplest patterns, repetitions, play a key role in data compression, such as we see every day in .zip files. More complicated patterns, involving repetitions and reversals, arise naturally in the study of genetic sequences in DNA or RNA, in so-called "DNA hairpins". Words avoiding patterns have also been proposed as a cryptographic tool.

Simple questions about which patterns can be avoided in long strings of symbols remain unanswered, but problems which had been previously unsolved for 20 or 40 years are starting to be resolved. In the same way that studying simple objects in arithmetic, such as prime numbers, has led to technical breakthroughs in encryption of banking transactions, understanding the basic mathematics of strings of symbols should continue to have importance in data compression, genetic analysis and information technology.