A note concerning the limit distribution of the quicksort algorithm
A note on -algebras.
A note on a conjecture of Duval and sturmian words
We prove a long standing conjecture of Duval in the special case of sturmian words.
A Note on a Conjecture of Duval and Sturmian Words
We prove a long standing conjecture of Duval in the special case of Sturmian words.
A note on a two dimensional knapsack problem with unloading constraints
In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin B, and a list L of n rectangular items, each item with a class value in {1,...,C}. The problem is to pack a subset of L into B, maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item a, items with higher class values can not block a. We present a (4 + ϵ)-approximation algorithm when the bin is a square. We also present (3 + ϵ)-approximation...
A note on antichains of words.
A note on certain ergodicity coeflcients
We investigate two ergodicity coefficients ɸ ∥∥ and τn−1, originally introduced to bound the subdominant eigenvalues of nonnegative matrices. The former has been generalized to complex matrices in recent years and several properties for such generalized version have been shown so far.We provide a further result concerning the limit of its powers. Then we propose a generalization of the second coefficient τ n−1 and we show that, under mild conditions, it can be used to recast the eigenvector problem...
A note on coinduction and weak bisimilarity for while programs
A note on Coinduction and Weak Bisimilarity for While Programs
An illustration of coinduction in terms of a notion of weak bisimilarity is presented. First, an operational semantics for while programs is defined in terms of a final automaton. It identifies any two programs that are weakly bisimilar, and induces in a canonical manner a compositional model . Next is proved by coinduction.
A note on comparison of Turing machines with computers
A note on complexity of algorithmic nets without cycles
A note on connections between 0L-languages and context-free languages
A note on constructing infinite binary words with polynomial subword complexity
Most of the constructions of infinite words having polynomial subword complexity are quite complicated, e.g., sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words w over a binary alphabet { a,b } with polynomial subword complexity pw. Assuming w contains an infinite number of a’s, our method is based on the gap function which gives the distances between consecutive b’s. It is known that if the gap function...
A note on domination in bipartite graphs
DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.
A note on domino shuffling.
A note on dual approximation algorithms for class constrained bin packing problems
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity , and items of different classes, each item with class and size . The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size . In...
A note on dual approximation algorithms for class constrained bin packing problems
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class ce and size se. The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size...
A note on equal powers of word morphisms
A note on exponential density of ETOL languages
A note on f-disjunctive languages.