On the lower bound for minimum comparison selection
On the matrices of central linear mappings
We show that a central linear mapping of a projectively embedded Euclidean -space onto a projectively embedded Euclidean -space is decomposable into a central projection followed by a similarity if, and only if, the least singular value of a certain matrix has multiplicity . This matrix is arising, by a simple manipulation, from a matrix describing the given mapping in terms of homogeneous Cartesian coordinates.
On the median-of- version of Hoare’s selection algorithm
On the median-of-k version of Hoare's selection algorithm
In Hoare's (1961) original version of the algorithm the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.
On the membership problem for pseudo-varieties of commutative semigroups.
On the M/G/1 retrial queue subjected to breakdowns
Retrial queueing systems are characterized by the requirement that customers finding the service area busy must join the retrial group and reapply for service at random intervals. This paper deals with the M/G/1 retrial queue subjected to breakdowns. We use its stochastic decomposition property to approximate the model performance in the case of general retrial times.
On the M/G/1 retrial queue subjected to breakdowns
Retrial queueing systems are characterized by the requirement that customers finding the service area busy must join the retrial group and reapply for service at random intervals. This paper deals with the M/G/1 retrial queue subjected to breakdowns. We use its stochastic decomposition property to approximate the model performance in the case of general retrial times.
On the minimum error in addition processes of positive floating-point numbers
On the number of Arnoux-Rauzy words
On the number of binary signed digit representations of a given weight
Binary signed digit representations (BSDR’s) of integers have been studied since the 1950’s. Their study was originally motivated by multiplication and division algorithms for integers and later by arithmetics on elliptic curves. Our paper is motivated by differential cryptanalysis of hash functions. We give an upper bound for the number of BSDR’s of a given weight. Our result improves the upper bound on the number of BSDR’s with minimal weight stated by Grabner and Heuberger in On the number of...
On the Number of Critical Free Contacts of a Convex Polygonal Object Moving in Two-Dimensional Polygonal Space.
On the number of descendants and ascendants in random search trees.
On the number of initial segments of a finite set of sequences (finite language)
On the number of iterations required by Von Neumann addition
We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.
On the number of iterations required by Von Neumann addition
We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.
On the Number of Minimal 1-Steiner Trees.
On the Number of Partitions of an Integer in the -bonacci Base
For each we consider the -bonacci numbers defined by for and for When these are the usual Fibonacci numbers. Every positive integer may be expressed as a sum of distinct -bonacci numbers in one or more different ways. Let be the number of partitions of as a sum of distinct -bonacci numbers. Using a theorem of Fine and Wilf, we obtain a formula for involving sums of binomial coefficients modulo In addition we show that this formula may be used to determine the number of partitions...
On the number of permutations admitting an th root.
On the number of squares in partial words
The theorem of Fraenkel and Simpson states that the maximum number of distinct squares that a word w of length n can contain is less than 2n. This is based on the fact that no more than two squares can have their last occurrences starting at the same position. In this paper we show that the maximum number of the last occurrences of squares per position in a partial word containing one hole is 2k, where k is the size of the alphabet. Moreover, we prove that the number of distinct squares in a partial...
On the Number of Views of Polyhedral Terrains.