# Strings and "co-subsequences"

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)

• Actually, I always thought the standard use is to say 'substring' for contiguous parts and 'subsequence' for not necessarily contiguous parts. Mar 15 '10 at 10:40
• You're absolutely right, I should have been more careful. I'm editing this right now to fix that. Mar 15 '10 at 10:58

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.

• this is a very good suggestion. Mar 15 '10 at 23:37
• Yes, I do find that better than what I proposed. By the way, this may be a bit off topic, but since I'm aware of that I'll just say it: one will need to be careful in a computational biology context, where the complement of a DNA string (a string over {A,C,G,T}) is something completely different (replace every occurrence of A with T and of C with G and conversely). Mar 16 '10 at 7:26

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

• Combinatorics of words is new?!? Mar 16 '10 at 1:12
• Thanks for all these references, I'll browse the ones I can find. Mar 16 '10 at 7:26

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.

• Thanks a lot, Lothaire's book has not helped, but I have yet to check the second reference. Mar 16 '10 at 7:27

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.

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".

• Yes, I was looking for "co(-)factor" in the books that Amy and Joseph suggested, but have not found a mention of that yet. Mar 16 '10 at 7:28