Abstract 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\}$$ { 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 $$\left| y \right| \le \left| x \right| $$ y ≤ x . We also provide a formalized parametric solution of the related equation $$x^jy^k = z^\ell $$ x j y k = z ℓ .

Combinatorics on Words is a rather young domain encompassing the study of words and formal languages. An archetypal example of a task in Combinatorics on Words is to solve the equation x ⋅ y = y ⋅ x, i.e., to describe words that commute. This contribution contains formalization of three important classical results in Isabelle/HOL. Namely i) the Periodicity Lemma (a.k.a. the theorem of Fine and Wilf), including a construction of a word proving its optimality; ii) the solution of the equation x^a ⋅ y^b = z^c with 2 ≤ a,b,c, known as the Lyndon-Schützenberger Equation; and iii) the Graph Lemma, which yields a generic upper bound on the rank of a solution of a system of equations. The formalization of those results is based on an evolving toolkit of several hundred auxiliary results which provide for smooth reasoning within more complex tasks.

We provide a reformulation and a formalization of the classical result by Juhani Karhum\"aki characterizing intersections of two languages of the form $\{x,y\}^*\cap \{u,v\}^*$. We use the terminology of morphisms which allows to formulate the result in a shorter and more transparent way, and we formalize the result in the proof assistant Isabelle/HOL.

A \itbf{cover} of a string $x = x[1..n]$ is a proper substring $u$ of $x$ such that $x$ can be constructed from possibly overlapping instances of $u$. A recent paper \cite{FIKPPST13} relaxes this definition --- an \itbf{enhanced cover} $u$ of $x$ is a border of $x$ (that is, a proper prefix that is also a suffix) that covers a {\it maximum} number of positions in $x$ (not necessarily all) --- and proposes efficient algorithms for the computation of enhanced covers. These algorithms depend on the prior computation of the \itbf{border array} $β[1..n]$, where $β[i]$ is the length of the longest border of $x[1..i]$, $1 \le i \le n$. In this paper, we first show how to compute enhanced covers using instead the \itbf{prefix table}: an array $π[1..n]$ such that $π[i]$ is the length of the longest substring of $x$ beginning at position $i$ that matches a prefix of $x$. Unlike the border array, the prefix table is robust: its properties hold also for \itbf{indeterminate strings} --- that is, strings defined on {\it subsets} of the alphabet $Σ$ rather than individual elements of $Σ$. Thus, our algorithms, in addition to being faster in practice and more space-efficient than those of \cite{FIKPPST13}, allow us to easily extend the computation of enhanced covers to indeterminate strings. Both for regular and indeterminate strings, our algorithms execute in expected linear time. Along the way we establish an important theoretical result: that the expected maximum length of any border of any prefix of a regular string $x$ is approximately 1.64 for binary alphabets, less for larger ones.