What string operations are basic in the sense that the other string operations can be represented in terms of them? Here is a list of string operations off the top of my head (not necessarily a complete list, and your addition is welcome):

  • reversal of a string
  • concatenation of two strings
  • repetition of a string a finite number of times
  • search/match a string inside another string
  • match and replace a string with another string inside a string
  • split a string, at some specified positions, or according to matching result of another string
  • taking a substring out of a string, according to specified positions (including taking prefix, or suffix), or according to matching result of another string
  • ...

1 Answer 1


There are many "complete bases" for operations on strings. One is based on the representation $$ \Sigma^* = \epsilon + \Sigma \Sigma^*. $$ In words, a string is either empty or is composed of a character and a string. In order to use this representation, we need the following functions:

  • nil – the empty string
  • cons(x,s) – the string consisting of the character x followed by the string s
  • null(s) – true if s is empty
  • car(s) – returns the first character of a non-empty string
  • cdr(s) – returns the string resulting from removing the first character of a non-empty string

The terminology is from Lisp; cdr is read could-er or cudder.

Another basis considers strings as arrays. There is a standard basis for reading strings:

  • len(s) – the length of s
  • s[i] – the character at position i

For writing strings there are several options. In the immutable case, one choice is:

  • "" – the empty string
  • str(x) – the string consisting of the character x
  • cat(s1,s2) – the string resulting from concatenating s1 and s2

If strings are allowed to be mutable, we can add an operation s[i] = x, changing the character at position i to be x.

One can think of many other bases. Some will be more efficient than others. It all depends on what exactly you are trying to capture, what your goal is.

  • $\begingroup$ I'd write "coulder" as "cudder"; "coulder" sounds like it would rhyme with "boulder". $\endgroup$ Jul 16, 2014 at 7:32

Your Answer

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

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