2
$\begingroup$

I work now a lot with strings of characters and other finite sequences and found that I need many times a good notation for "cutting the end" a string. If $a$ is a finite sequence and $a'$ is its right end, then there is a sequence $x$ such that $a = x a'$ (where the product is defined by concatenation). What I would like to have is a suggestive notation for $x$: $x$ might be $a$ "minus" $a'$, or $a$ "divided by $a'$, if we view the set of all strings as a semigroup. I have therefore thought of writing $x$ as $a / a'$ but am not completely happy with it. Obvoiusly I need also a notation for "cutting at the left end"; by continuing with the previous idea the notation $a' \setminus a$ could stand for the solution of $a = a' x$, but it collides a bit with the notation for set difference.

So far I have thought, and my question is: Is there a good notation for these concepts already in use in some areas of mathematics or computer science, or has someone else already defined a suggestive notation?

P.S. And I also would like to have a notation for the "overlapping concatenation" of strings: If $a = a'x$ and $b = xb'$, what is $a'xb'$?


Addition, 2014:

After reading the answers so far, and not being satisfied with them, I came up with the following scheme:

  • Right ends: If $a = a' x$, then I write $a \mathrel{//} x$ to express that $x$ appears at the right end of $a$. I also write $a' = a / x$ for the result of cutting $x$ from the right end of $a$.

  • Left ends: If $a = x a'$, then I write $x \mathrel{\backslash\backslash} a$ to express that $x$ appears at the left end of $a$. I also write $a' = x \setminus a$ for the result of cutting $x$ from the left end of $a$.

  • Overlapping product: If $a = a'x$ and $b = x b'$ (or $a \mathrel{//} x \mathrel{\backslash\backslash} b$ in the new notation), then $a' x b' = a \mathbin{\langle x\rangle} b$.

The result is a workable notation and aesthetically pleasing (at least for me).

$\endgroup$
4
  • $\begingroup$ In combinatorics on words, if $a=xa'$, then $x$ and $a'$ are subwords (or factors) of $a$, $x$ is a prefix of $a$, and $a'$ is a suffix of $a$. If $x$ is not empty, then it is a proper prefix of $a$. $\endgroup$
    – JRN
    Apr 13, 2012 at 10:58
  • $\begingroup$ Try adding the combinatorics-on-words tag to your question. $\endgroup$
    – JRN
    Apr 13, 2012 at 11:16
  • 3
    $\begingroup$ If you are already interpreting concatenation as a product, then you can use inverses: $x=a(a')^{-1}$, $(a')^{-1}a$, $a'xb'=ax^{-1}b$. This notation is common in word groups, although I am stretching it a little bit here. Note that the defintion of your "overlapping concatenation" operator already uses $x$ implicitly, so there should be nothing wrong in spelling it out explicitly. $\endgroup$ Apr 13, 2012 at 11:22
  • 1
    $\begingroup$ @Joel: Thanks for the hint - I have added the tag. $\endgroup$
    – user22882
    Apr 14, 2012 at 8:24

1 Answer 1

6
$\begingroup$

A good reference is "G. Rozenberg, A. Salomaa Eds., Handbook of Formal Languages - Vol 1 Word Language Grammar, Springer, 1997" in Chapter 6: Combinatorics of Words:

Let $\sum$ be a finite alphabet. If $u$ is a word then $u=a_{1}\ldots a_{n}$, with $a_{i}\in\sum$.

For a pair $\left(u,v\right)$ of words we define four relations:

$u$ is a prefix of $v$, if there exists a word $z$ such that $v=uz$;

$u$ is a suffix of $v$, if there exists a word $z$ such that $v=zu$;

$u$ is a factor of $v$, if there exists words $z$ and $z'$ such that $v=zuz'$;

$u$ is a subword of $v$, if $v$ as a sequence of letters contains $u$ as a subsequence, i.e., there exist words $z_{1},\ldots,z_{t}$ and $y_{0},\ldots,y_{t}$ such that $u=z_{1}\ldots z_{t}$ and $v=y_{0}z_{1}y_{1}\ldots z_{t}y_{t}$.

Sometimes factors are called subwords, and then subwords are called sparse subwords.

If $v=uz$ we write $u=vz^{-1}$ or $z=u^{-1}v$, and say that $u$ is the right quocient of $v$ by $z$, and that $z$ is the left quotient of $v$ by $u$.

For the "overlapping concatenation" of strings: $b'=x^{-1}b$ and $a'=ax^{-1}$. Then $a'xb'=ax^{-1}b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.