|
This article is cited in 1 scientific paper (total in 1 paper)
The Shannon function of the complexity of interval search on a Boolean cube in the class of trees
T. D. Blaivas
Abstract:
For the problem of interval search on the Boolean cube,
we investigate the behaviour of the Shannon function
in the class of tree-like circuits called information trees.
It is shown that for databases of cardinality coinciding in order
with cardinality of the Boolean cube
the Shannon function is equal in order to the optimal complexity in the class
of balanced tree-like circuits.
For databases of cardinality less in order
than the cardinality of the Boolean cube
we give the asymptotics of the logarithm of the Shannon function.
Received: 23.08.2005
Citation:
T. D. Blaivas, “The Shannon function of the complexity of interval search on a Boolean cube in the class of trees”, Diskr. Mat., 18:2 (2006), 111–122; Discrete Math. Appl., 16:3 (2006), 259–270
Linking options:
https://www.mathnet.ru/eng/dm50https://doi.org/10.4213/dm50 https://www.mathnet.ru/eng/dm/v18/i2/p111
|
Statistics & downloads: |
Abstract page: | 619 | Full-text PDF : | 204 | References: | 51 | First page: | 4 |
|