Let $\mathscr F(X)$ be the free monoid on an alphabet $X$, the carrier set of $\mathscr F(X)$ being the union of $X^{\times k}$ (the Cartesian product of $k$ copies of $X$) as $k$ ranges over $\mathbb N$ (the non-negative integers). We will refer to an element of $\mathscr F(X)$ as an $X$-word; and use the symbol $\ast$ for the operation (of word concatenation) in $\mathscr F(X)$ and $\varepsilon$ for the empty word (namely, the identity of $\mathscr F(X)$).
Given an $X$-word $\mathfrak u$, there is a unique $k \in \mathbb N$, called the (word) length of $\mathfrak u$ and herein denoted by $\|\mathfrak u\|$, such that $\mathfrak u \in X^{\times k}$: If $k \ge 1$, then there are uniquely determined $x_1, \ldots, x_k \in X$ (named the letters of $\mathfrak u$) such that $\mathfrak u = x_1 \ast \cdots \ast x_k$; and for each index $i \in [\![ 1, k ]\!]$ (the discrete interval between $1$ and $k$), we write $\mathfrak u[i]$ for the $i$-th letter of $\mathfrak u$.
Now suppose that $\mathfrak v$ and $\mathfrak w$ are both $X$-words. There are at least three (alternative) ways to define what it means for $\mathfrak v$ to be a subword of $\mathfrak w$:
- $\mathfrak v$ divides $\mathfrak w$ in $\mathscr F(X)$, that is, $\mathfrak w = \mathfrak s \ast \mathfrak v \ast \mathfrak t$ for some $\mathfrak s, \mathfrak t \in \mathscr F(X)$.
- There is a (strictly) increasing function $\sigma \colon [\![1, \|\mathfrak v\| ]\!] \to [\![1, \|\mathfrak w\| ]\!]$ such that $\mathfrak v[i] = \mathfrak w[\sigma(i)]$ for each $i \in [\![1, \|\mathfrak v\| ]\!]$ (note that this condition is vacuously satisfied when $\mathfrak v = \varepsilon$).
- Same as the previous definition, except that $\sigma$ is required to be injective (rather than increasing).
My question is whether there is any well-established terminology that makes it possible to distinguish each kind of subword from the others. I've seen subwords of type 2 being called scattered subwords (and I myself am sticking to this term in my writings).
Edit 1. In a comment to the OP, Vladimir Dotsenko asked, "Does the situation 3 really appear in a meaningful way?" Here, I'll try to address his question.
Suppose that $X$ is a subset of a (multiplicatively written) monoid $H$. An $X$-factorization of an element $h \in H$ is then an $X$-word $\mathfrak u$ such that $h = \pi(\mathfrak u)$, where $\pi$ is the (so-called) factorization homomorphism of $H$, namely, the unique extension of the identity function on $H$ to a monoid homomorphism $\mathscr F(H) \to H$. For various reasons, it is somehow interesting (from the point of view of the arithmetic theory of monoids) to endow $H$ with a preorder (i.e., a reflexive and transitive binary relation) $\preceq$ and to look at the $X$-factorizations of an element $h \in H$ that are minimal with respect to the (so-called) shuffling preorder $\sqsubseteq$, that is, the binary relation on $\mathscr F(H)$ defined by $\mathfrak u \sqsubseteq \mathfrak v$, for some $H$-words $\mathfrak u$ and $\mathfrak v$, if and only if there is an injective function $\sigma \colon [\![ 1, \|\mathfrak u\| ]\!] \to [\![ 1, \|\mathfrak v\| ]\!]$ such that $\mathfrak u[i] \preceq \mathfrak v[\sigma(i)] \preceq \mathfrak u[i]$ for each $i \in [\![ 1, \|\mathfrak u\| ]\!]$. Minimal $X$-factorizations can then be used to forge the notions of 'minimal unique factorization', 'minimal factorization length', etc., which (generalize and) work somewhat better than the corresponding notions in the classical theory (where the preorder $\preceq$ is the divisibility preorder on $H$ and $\sqsubseteq$ is (almost always) implicitly assumed to be the relation of $\sqsubseteq$-equivalence), especially in those situations where the nature of $H$ gives rise to 'blow-up phenomena' that make classical 'metric invariants' (such as sets of lengths and their unions, elasticities, distances, etc.) essentially meaningless. Note, in particular, that two $X$-words are $\sqsubseteq$-equivalent if and only if one is a permutation of the other modulo $\preceq$-equivalence: This is ultimately a generalization of the fact that, in the basic setting of the integers under multiplication, two prime factorizations of the same element are considered the same if and only if they differ only in the order of the factors and up to associates.
