Ryoma Sin'ya. A quantitative approach to the primitive words conjecture
Channel: Computational Logic and Applications
Date: 2020-10-12

15th Workshop
Computational Logic and Applications (https://cla.tcs.uj.edu.pl/)
12-13 October 2020

Speakers: Ryoma Sin'ya
Title: A quantitative approach to the primitive words conjecture
Abstract:

A non-empty word w is said to be primitive if it is not a power of a shorter words, i.e., (w≠u^n for any |u|\lt |w| and n\gt 1). The notion of primitivity of words plays a central role in algebraic coding theory and combinatorics on words. Whether the set of all primitive words Q

is context-free or not is a well-known long-standing open problem posed by Dömösi, Horváth and Ito in 1991.

In this talk, we give a brief intuition why this problem is hard to solve, based on a quantitative observation. In particular, we describe a special quantitative property that, although Q
is "very large" (i.e., density one), any regular subset of Q is "very small" (i.e., density zero).