Charles Explorer logo
🇨🇿

Binary Codes that do not Preserve Primitivity

Publikace na Matematicko-fyzikální fakulta |
2023

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

A set of words X is not primitivity-preserving if there is a primitive list of length at least two of elements from X whose concatenation is imprimitive. Here, a word or list is primitive if it is not equal to a concatenation of several copies of a shorter word or list, and imprimitive otherwise.

We formalize a full characterization of such two-element sets {x, y} in the proof assistant Isabelle/HOL. The formalization is based on an existing proof which we analyze and simplify using some innovative ideas.

Part of the formalization, interesting on its own, is a description of the ways in which the square xx can appear inside a concatenation of words x and y if |y| = |x|. We also provide a formalized parametric solution of the related equation x(j)y(k) = z(l).