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
1987
0 references
complexity measures of symbol sequences
0 references
supercomplex strings
0 references
0.8532747626304626
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