1
$\begingroup$

A string is something like: "ad939-0x!", or "mary had a LittLE lambD". There's a character set, and you glue stuff together from the character set to build strings.

Have there been any useful definitions for operations on strings that allow strings to form a vector space?

$\endgroup$
  • $\begingroup$ Polynomials can be seen as strings. $\endgroup$ – Git Gud Feb 7 '15 at 18:08
  • $\begingroup$ @GitGud Polynomials are encoded by vectors, they are not elements of vectors. $\endgroup$ – user89 Feb 7 '15 at 18:58
1
$\begingroup$

Formal Language theory studies strings and operations among them. Kleene algebra [1] with operations of composition (concatenation) and union forms a semiring/dioid -- this is generalization of [number] field that lies in the foundation of Linear Algebra. Solving linear systems in dioids is a central problem in the theory [2] with one of the most important applications -- language recognition.

To give you a flavor of the theory, given a string of characters one may choose to ignore character positions and focus only on number of character occurrences only. This map is well studied and its range in your case is 26-dimensional Parikh Space. For example, the string "baaab" maps to vector (3,2,0,...), while "cbc" maps to (0,1,2,...). Their concatenation "baaab"+"cbc" maps to vector sum (3,3,2,...).

  1. Kozen, Dexter. "CS786 Spring 04, Introduction to Kleene Algebra"
  2. GRAPHS, DIOIDS AND SEMIRINGS by Michel Gondran, Michel Minoux
$\endgroup$

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.