0
$\begingroup$

I want to represent a set of any substrings which come from an original string with constraint that all substrings should not be overlapped. To be more clear please consider the example below:

e.g.

orignal_string = "ABCDEFG"      // this can be any characters.
substring = {"ABC", "DE", "FG"} // right.
substring = {"A", "BCD"}        // right.
substring = {"BC", "FG"}        // right.
substring = {"AB", "ABC"}       // wrong, AB are overlapped.
substring = {"ABCD", "CDEFG"}   // wrong, CD are overlapped.

How to represent this in formal notation?

|cite|improve this question
$\endgroup$
  • $\begingroup$ $\forall axb, dxc \in S: x = \epsilon$? $S$ is the set in question, the assertion reads: for any two elements of $S$, the only substring that they share is the empty string. $\endgroup$ – wvxvw Apr 8 '16 at 14:37
  • 1
    $\begingroup$ What exactly are you trying to represent? The set of all such strings? Some specific set of non-overlapping strings? The property of two strings, "These two strings don't overlap"? $\endgroup$ – David Richerby Apr 8 '16 at 15:33
  • 3
    $\begingroup$ Also, what's wrong with just writing in words "have no nonempty common substring"? Don't use notation for things that are more easily expressed in words. $\endgroup$ – David Richerby Apr 8 '16 at 15:34
  • $\begingroup$ @DavidRicherby I try to represent set of any substrings that not overlapped. $\endgroup$ – fronthem Apr 8 '16 at 15:49
  • 1
    $\begingroup$ @voidnich You can't define a set without saying what's in it. So it sounds like you're looking to define the property. Again, what's wrong with doing it in words? You already know how to do that and your reader will almost certainly prefer "share no nonempty common substring" to a pile of symbols that will take them tens of seconds to decode. $\endgroup$ – David Richerby Apr 8 '16 at 16:16
2
$\begingroup$

Idea: represent substrings by their resp. start and end index.

Let $w = w_1 \dots w_n \in \Sigma^*$ a string for some alphabet $\Sigma$. Denote (indexed) substrings of $w$ by pairs $(i,j)$ with $1 \leq i \leq j \leq n$. The actual sequence of symbols represented by $(i,j)$ would be $w_{i,j} = w_i \dots w_j \in \Sigma^*$.

Denote the set of all indexed substrings of $w$ by

$\qquad\displaystyle S_w = \{ (wi, j) \mid 1 \leq i \leq j \leq n \} \subseteq [1..n]^2$.

Note how $\{ w_{i,j} \mid (i,j) \in S_w\}$ is can have fewer elements due to duplicate substrings.

Non-overlapping substrings

Two indexed substrings $(i,j), (k,l) \in S_w$ with $i \leq k$ overlap if and only if $k \leq j$. Otherwise, we call them non-overlapping.

Sets of non-overlapping substrings

A set $A \subseteq S_w$ of substrings of $w$ is non-overlapping if and only if

$\qquad \forall\, u, c \in A.\ u$ and $v$ do not overlap¹.

The set of all non-overlapping sets of substrings

The set of all non-overlapping sets of substrings is

$\qquad \mathcal{N}_w = \{ A \subseteq S_w \mid A \text{ non-overlapping²} \}$.

  1. If you so desire, input the formal definition of "do not overlap" here, i.e. $u = w_{i,j}$ and $v = w_{k,l}$ with $i \leq k$ and $k > j$. Or invent notation for the predicate "do overlap", e.g. $\operatorname{overlap}(u,v)$ or $\eta(u,v)$ or ...

  2. Again, you can replace "non-overlapping" with the definition. I don't think that makes things more clear. The whole reason for defining shorthand is to express more complicated things easily and succinctly, after all.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If this is overkill is, of course, a matter of taste, style, and a question of what you are going to do. If you want students to train creating rigorous proofs, a formal definition like this is necessary (for them to unfold). If you are to publish an article, probably not. $\endgroup$ – Raphael♦ Apr 9 '16 at 14:27
  • $\begingroup$ Then there is the interseting difference between substring and occurrence of a substring. Do AB and BC overlap in the string ABABC? $\endgroup$ – Hendrik Jan Apr 10 '16 at 22:53
  • $\begingroup$ @HendrikJan With my definition, it does not make sense to identify substrings without its indices. In your example $w = ABABC$, $w_{1,2}$ and $w_{4,5}$ do not overlap, but $w_{3,4}$ and $w_{4,5}$ do. Never mind that $w_{1,2} = w_{3,4}$. Do you think that can be a problem? Should we create a new "type" for "indexed substrings"? $\endgroup$ – Raphael♦ Apr 11 '16 at 8:11
  • $\begingroup$ Formally I think that is a debatable point, depending on the context. Here it seems that the indexes are needed indeed. Your $S_w$ looks like a set, but does that set distinguish $w_{1,2}$ from $w_{3,4}$, does it contain $AB$ "twice"? (These are open questions, I do not want to solve that for this question, which was not very explicit on these details.) $\endgroup$ – Hendrik Jan Apr 11 '16 at 9:05
  • $\begingroup$ @HendrikJan You are right; I implicitly dealt with multisets sometimes. That's no good, and I fixed it now. Thanks! $\endgroup$ – Raphael♦ Apr 11 '16 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.