arvutiteaduse instituudi lõputööde teemade register

Repeat-free codes
Organisatsiooni nimiCoding and Information Transmission Group
KokkuvõteIn this thesis topic we are going to investigate repeat-free codes. A word c of length n over a finite alphabet A is called (n,k) repeat-free if every word of length k occurs at most once as a subword of c. Here a word w=w_1w_2...w_k occurs in c at location i if c_{i+j-1}=w_j for j=1, ..., k. A collection C of words of length n over A is called an (n,k) repeat-free code over A if every word c in C is (n,k)-repeat-free. More general, a code C is called (n,k) (t+1)-repeat-free if in each code word, every word of length k occurs at most t times.
Some important questions are the following.

1. What is the number N_{n,k} of (n,k) repeat-free words of length n? And what is
the number N_{n,k,t} of (n; k) (t + 1)-repeat-free words?

2. How should we encode into repeat-free words?

Already the notion of a (t + 1)-repeat-free code seems new here.
The aim is to read some papers on this subject and then to investigate the above questions.
Lõputöö kaitsmise aasta2022-2023
JuhendajaHenk D.L. Hollmann, Vitaly Skachek, Ago-Erik Riet
Suhtlemiskeel(ed)inglise keel
Nõuded kandideerijaleThe topic is suitable both for a bachelor thesis and for a master thesis.
Some background in combinatorics would be helpful but is not required.
Tase Bakalaureus, Magister
Märksõnad #combinatorics, #graph theory
Kandideerimise kontakt
Nimi Henk D.L. Hollmann
Tel +31 619489142