Page 1 Next

Displaying 1 – 20 of 888

Showing per page

5-abelian cubes are avoidable on binary alphabets

Robert Mercaş, Aleksi Saarela (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.

A backward selection procedure for approximating a discrete probability distribution by decomposable models

Francesco M. Malvestuto (2012)

Kybernetika

Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution p over a finite set V of n discrete variables and a positive integer k , find a decomposable model with tree-width k that best fits p . If is the generating hypergraph of a decomposable model and p is the estimate of p under the model, we can measure...

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2011)

RAIRO - Theoretical Informatics and Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

A density version of the Carlson–Simpson theorem

Pandelis Dodos, Vassilis Kanellopoulos, Konstantinos Tyros (2014)

Journal of the European Mathematical Society

We prove a density version of the Carlson–Simpson Theorem. Specifically we show the following. For every integer k 2 and every set A of words over k satisfying lim sup n | A [ k ] n | / k n > 0 there exist a word c over k and a sequence ( w n ) of left variable words over k such that the set c { c w 0 ( a 0 ) . . . w n ( a n ) : n and a 0 , . . . , a n [ k ] } is contained in A . While the result is infinite-dimensional its proof is based on an appropriate finite and quantitative version, also obtained in the paper.

A distributed transportation simplex applied to a Content Distribution Network problem

Rafaelli de C. Coutinho, Lúcia M. A. Drummond, Yuri Frota (2014)

RAIRO - Operations Research - Recherche Opérationnelle

A Content Distribution Network (CDN) can be defined as an overlay system that replicates copies of contents at multiple points of a network, close to the final users, with the objective of improving data access. CDN technology is widely used for the distribution of large-sized contents, like in video streaming. In this paper we address the problem of finding the best server for each customer request in CDNs, in order to minimize the overall cost. We consider the problem as a transportation problem...

A finite word poset.

Erdős, Péter L., Sziklai, Péter, Torney, David C. (2001)

The Electronic Journal of Combinatorics [electronic only]

A general upper bound in extremal theory of sequences

Martin Klazar (1992)

Commentationes Mathematicae Universitatis Carolinae

We investigate the extremal function f ( u , n ) which, for a given finite sequence u over k symbols, is defined as the maximum length m of a sequence v = a 1 a 2 . . . a m of integers such that 1) 1 a i n , 2) a i = a j , i j implies | i - j | k and 3) v contains no subsequence of the type u . We prove that f ( u , n ) is very near to be linear in n for any fixed u of length greater than 4, namely that f ( u , n ) = O ( n 2 O ( α ( n ) | u | - 4 ) ) . Here | u | is the length of u and α ( n ) is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...

Currently displaying 1 – 20 of 888

Page 1 Next