Strings and "co-subsequences"

Question

Let $S$ be a string over some alphabet $\Sigma$. It is well known that a substring of $S$ is commonly defined as a sequence of contiguous elements from $S$, while a subsequence of $S$ is a sequence made of non necessarily contiguous elements from $S$ (e.g. if $S="123465835"$, then $"4658"$ is a substring of $S$ while $"1236"$ is a subsequence of $S$). But is there a word to refer to subsequences that can be obtained from $S$ by removing an arbitrary substring (e.g. $"12835"$)?

(this concept seems complementary to that of a subsequence, hence the conjectured "co-subsequence" in the title -- although "co-substring" might be a good choice too)

Answer 1

Since you are taking the complement of a substring, and it appears that there may be no firmly established terminology, I propose:

• a substring complement is what remains after deleting a substring,
• and more generally, a subsequence complement is what remains after deleting a subsequence.

Thus, one may refer to the substring complement of s in t, and use the notation t - s, or $t \setminus s$, with the same notation for the subsequence.

I would prefer this natural language terminology over the alternative co-substring and co-subsequence, which sound unnecessarily technical to my ear, but this difference may be slight.

It does seem worthwhile, however, to distinguish between the two cases, and so I would argue against using the term co-subsequence, as you suggested in your question, to refer to the substring complement.

Answer 2

The combinatorics of words (strings) is a relatively new area of interest for mathematicians and computer scientists so perhaps it is not surprising that there is somewhat wide variation in terminology for this emerging field. However, there are already a wide variety of books that treat questions in this area:

Jewels of Stringology, Maxime Crochemore and Wojciech Rytter

Algorithms on strings, trees, and sequences, Dan Gusfield

Combinatorics on Words, M. Lothaire

Applied Combinatorics on Words, M. Lothaire

Sequence Comparison, Kun-Mao Chao and Louxin Zhang

Answer 3

I work in the area of combinatorics on words and am not aware of any existing terminology for the type of subsequence that you are tentatively calling a "co-subsequence", so you can probably stick with this name if you like.

By the way, Joseph provided a nice list of books on words/strings. Here are two more that I would highly recommend:

• M. Lothaire, "Algebraic Combinatorics on Words", vol. 90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2002

• J.-P. Allouche & J. Shallit, "Automatic Sequences: Theory, Applications, Generalizations", Cambridge University Press, 2003

The first book and two others in the Lothaire series are freely available here.

Answer 4

I have not heard of that. I think if a string $w$ a concatenation of two strings $w = uv$ then $u$ is sometimes called a prefix and $v$ a suffix. Hence each co-sequence can be written as a concatenation of a prefix and a suffix of the original string.

Answer 5

Snce substrings are also called "factors" in formal language theory, the name "cofactor" may be clearer than "co-substring". However, be aware of potentially conflicting uses for "cofactor".