Results 11 to 20 of about 893,053 (74)
The Degree Distribution of Thickened Trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 We develop a combinatorial structure to serve as model of random real world networks. Starting with plane oriented recursive trees we substitute the nodes by more complex graphs.
Michael Drmota +2 more
doaj +1 more source
Branching processes in random environment die slowly [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 Let $Z_n,n=0,1,\ldots,$ be a branching process evolving in the random environment generated by a sequence of iid generating functions $f_0(s),f_1(s),\ldots,$ and let $S_0=0$, $S_k=X_1+ \ldots +X_k,k \geq 1$, be the associated random walk with $X_i=\log ...
Vladimir Vatutin, Andreas Kyprianou
doaj +1 more source
Hopcroft's automaton minimization algorithm and Sturmian words [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 This paper is concerned with the analysis of the worst case behavior of Hopcroft's algorithm for minimizing deterministic finite state automata. We extend a result of Castiglione, Restivo and Sciortino.
Jean Berstel +2 more
doaj +1 more source
Polynomial tails of additive-type recursions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 Polynomial bounds and tail estimates are derived for additive random recursive sequences, which typically arise as functionals of recursive structures, of random trees, or in recursive algorithms.
Eva-Maria Schopp
doaj +1 more source
Concentration of measure and mixing for Markov chains [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 We consider Markovian models on graphs with local dynamics. We show that, under suitable conditions, such Markov chains exhibit both rapid convergence to equilibrium and strong concentration of measure in the stationary distribution.
Malwina Luczak
doaj +1 more source
Small parts in the Bernoulli sieve [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 Sampling from a random discrete distribution induced by a 'stick-breaking' process is considered. Under a moment condition, it is shown that the asymptotics of the sequence of occupancy numbers, and of the small-parts counts (singletons, doubletons, etc)
Alexander Gnedin +2 more
doaj +1 more source
The size of random fragmentation intervals [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 Two processes of random fragmentation of an interval are investigated. For each of them, there is a splitting probability at each step of the fragmentation process whose overall effect is to stabilize the global number of splitting events. More precisely,
Rafik Aguech
doaj +1 more source
Simple conditions for the transformation of dynamical coordinates into canonical ones in Hamiltonian dynamics [PDF]
Open Communications in Nonlinear Mathematical PhysicsWe obtain conditions, which when fulfilled, permit to transform the coordinates of a dynamical system into pairs of canonical ones for some Hamiltonian system.
Patrick Cassam-Chenaï
doaj +1 more source
A Markov Chain Algorithm for determining Crossing Times through nested Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 According to the by now established theory developed in order to define a Laplacian or ― equivalently ― a Brownian motion on a nested fractal, one has to solve certain renormalization problems.
Uta Freiberg, Christoph Thäle
doaj +1 more source
The register function for lattice paths [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 The register function for binary trees is the minimal number of extra registers required to evaluate the tree. This concept is also known as Horton-Strahler numbers. We extend this definition to lattice paths, built from steps $\pm 1$, without positivity
Guy Louchard, Helmut Prodinger
doaj +1 more source