Talk:Subsequence

From Wikipedia, the free encyclopedia

This article incorporates material from PlanetMath, which is licensed under the GFDL.

This is not right. A subsequence is a subsequence of something (of another sequence). At the moment it is an oxymoron - it says that it doesn't contain some of its own elements. --Zero 22:46, 31 Mar 2004 (UTC)

[edit] Sequence vs string

An edit 2006 19:22:35 stating A subsequence is a more general term than a substring, which is a consecutive part of the original string. was reverted with the reason revert, a string and a sequence is not the same thing as far as I know. I never heard of a subsequence of consecutive terms to be called a substring. References?

Both the terms string (computer science) and sequence are used for a list of objects, where the order of the objects matter, and an object may occur multiple times. I guess the difference in usage between the words is that the term string is usually not used when the objects are not symbols. The term string is also often used to denote the more spesific meaning a sequence of ASCII characters in a computer program.

From Gusfield, Algorithms on strings trees and sequences, 1st edition, page 4: ..., the words "string" and "sequence" are often used synomymously, particularly in the biological literature. This can be the source of much confusion because "substrings" and "subsequences" are very different objects... and The characters in a substring of S must occur contiguously in S, whereas characters in a subsequence might be intersped with characters not in the subsequence. See also longest common subsequence problem and longest common substring problem.

Nils Grimsmo 06:52, 30 March 2006 (UTC)

Right, so the words string and substring are usually used in computer science and related, but not in other areas, like mathematics. As such, that usage is much more particular than the usage of sequence, which is why mentioning substrings here would not be as appropriate I think.
In short, talking about a subsequence of a string is I think fine at all times, talking about the substring of a sequence is not accepted terminology except in computer science. Oleg Alexandrov (talk) 15:54, 30 March 2006 (UTC)
But people confusing the terms subsequence and substring is a problem in computer science. So maybe it is appropriate to state something like In computer science, the term string is often used as a synonym for a sequence, but it is important to note that substring and subsequence are not synonyms. Substrings are consecutive parts of a string, while subsequences need not be. This means that a substring of a string is always a subsequence of the string, but the opposite is not true. -- Nils Grimsmo 17:04, 30 March 2006 (UTC)
Yes, writing a text like that, starting with "in computer science" makes sense to me. Probably not in the very first introductory paragraph, but somewhere in the text where you find appropriate. Oleg Alexandrov (talk) 00:19, 31 March 2006 (UTC)
Done. Nils Grimsmo 07:29, 31 March 2006 (UTC)
Thanks, your addition is very well-written. Oleg Alexandrov (talk) 16:51, 31 March 2006 (UTC)