Extendibility and growth of words avoiding patterns

避免模​​式的单词的可扩展性和增长

• 批准号: RGPIN-2017-03901
• 负责人: Currie, James
• 金额: $ 1.02万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=648428
• 关键词: Extendibility; growth; words; avoiding; patterns

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.

在现代世界中，在小字母表上的长序列符号具有基本的重要性。无论我们是在考虑互联网上的0和1的流，还是考虑由字母A，C，G，T组成的长DNA序列，理解符号串的数学是非常重要的。本研究研究了长串符号中的不规则性和不规则性，确定哪些模式必须始终出现，哪些可以避免。最简单的模式，重复，在数据压缩中起着关键作用，例如我们每天在.zip文件中看到的。在研究DNA或RNA中的遗传序列时，自然会出现更复杂的模式，包括重复和反转，即所谓的“DNA发夹”。单词避免模式也被提议作为加密工具。在一长串的符号中，哪些模式可以避免，这个简单的问题仍然没有答案，但是以前20或40年没有解决的问题开始得到解决。就像研究简单的算术对象，如素数，导致了银行交易加密的技术突破一样，理解符号串的基本数学应该继续在数据压缩，遗传分析和信息技术中具有重要意义。