Strings and "co-subsequences" - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T10:15:18Z http://mathoverflow.net/feeds/question/18258 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18258/strings-and-co-subsequences Strings and "co-subsequences" Anthony Labarre 2010-03-15T08:42:47Z 2010-03-15T23:24:39Z <p>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"\$)?</p> <p>(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)</p> http://mathoverflow.net/questions/18258/strings-and-co-subsequences/18259#18259 Answer by Tomaž Pisanski for Strings and "co-subsequences" Tomaž Pisanski 2010-03-15T09:14:49Z 2010-03-15T09:14:49Z <p>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. </p> http://mathoverflow.net/questions/18258/strings-and-co-subsequences/18262#18262 Answer by Joseph Malkevitch for Strings and "co-subsequences" Joseph Malkevitch 2010-03-15T12:30:26Z 2010-03-15T12:30:26Z <p>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:</p> <p>Jewels of Stringology, Maxime Crochemore and Wojciech Rytter</p> <p>Algorithms on strings, trees, and sequences, Dan Gusfield</p> <p>Combinatorics on Words, M. Lothaire</p> <p>Applied Combinatorics on Words, M. Lothaire</p> <p>Sequence Comparison, Kun-Mao Chao and Louxin Zhang</p> http://mathoverflow.net/questions/18258/strings-and-co-subsequences/18266#18266 Answer by Amy Glen for Strings and "co-subsequences" Amy Glen 2010-03-15T13:40:35Z 2010-03-15T14:27:43Z <p>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.</p> <p>By the way, Joseph provided a nice list of books on words/strings. Here are two more that I would highly recommend:</p> <ul> <li><p>M. Lothaire, "Algebraic Combinatorics on Words", vol. 90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2002</p></li> <li><p>J.-P. Allouche &amp; J. Shallit, "Automatic Sequences: Theory, Applications, Generalizations", Cambridge University Press, 2003</p></li> </ul> <p>The first book and two others in the Lothaire series are freely available <a href="http://www-igm.univ-mlv.fr/~berstel/Lothaire/index.html" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/18258/strings-and-co-subsequences/18322#18322 Answer by Joel David Hamkins for Strings and "co-subsequences" Joel David Hamkins 2010-03-15T23:23:04Z 2010-03-15T23:23:04Z <p>Since you are taking the complement of a substring, and it appears that there may be no firmly established terminology, I propose:</p> <ul> <li>a <em>substring complement</em> is what remains after deleting a substring, </li> <li>and more generally, a <em>subsequence complement</em> is what remains after deleting a subsequence.</li> </ul> <p>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.</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/18258/strings-and-co-subsequences/18323#18323 Answer by mathy for Strings and "co-subsequences" mathy 2010-03-15T23:24:39Z 2010-03-15T23:24:39Z <p>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".</p>