Question

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'$?

Answer 1

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