No label defined (Q3814828)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4085051
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4085051

      Statements

      0 references
      1987
      0 references
      complexity measures of symbol sequences
      0 references
      supercomplex strings
      0 references
      Given two strings \(x=a_ 1a_ 2...a_ r\), \(y=b_ 1b_ 2...b_ s\) over some alphabet V, we say that x is a d-subword of y (d is a given positive integer) if there are indices \(i_ 1\), \(i_ 2,..,i_ r\) such that \(1\leq i_ j\leq s,\quad 1\leq i_{j+1}-i_ j\leq d,\) and \(a_ j=b_{i_ j}\) for all j. Denote by S(x,d) the set of all d-subwords of x. Then, the d-complexity of the string x is \[ K_ d(x)=\sum^{| x|}_{i=1}card(S(x,d)\cap V^ i). \] The paper gives motivations for such a measure, discusses many detailed examples, proposes variants (divided, modified, and normalized d-complexities), finds lower and upper bounds, looks for supercomplex strings and so on.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references