MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$. – Joel Reyes Noche Apr 13 '12 at 10:58
Try adding the combinatorics-on-words tag to your question. – Joel Reyes Noche Apr 13 '12 at 11:16
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. – Federico Poloni Apr 13 '12 at 11:22
@Joel: Thanks for the hint - I have added the tag. – rem Apr 14 '12 at 8:24
up vote 6 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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