Search results for "Random"

Erratum to “Testing for selectivity in the dependence of random variables on external factors” [J. Math. Psych. 52 (2008) 128–144]

2010

On the listing and random generation of hybrid binary trees

1994

We consider in this paper binary trees whose internal nodes are either associative or non-associative. Hybrid binary trees are equivalence classes with respect to the associative property. We count, list and generate randomly hybrid binary trees using Fibonacci numbers.

Generation of Valid Labeled Binary Trees

2003

International audience; Generating binary trees is a well-known problem. In this paper, we add some constraints to leaves of these trees. Such trees are used in the morphing of polygons, where a polygon P is represented by a binary tree T and each angle of P is a weight on a leaf of T. In the following, we give two algorithms to generate all binary trees, without repetitions, having the same weight distribution to their leaves and representing all parallel polygons to P.

On the existence of conditionally invariant probability measures in dynamical systems

2000

Let T : X→X be a measurable map defined on a Polish space X and let Y be a non-trivial subset of X. We give conditions ensuring the existence of conditionally invariant probability measures to non-absorption in Y. For dynamics which are non-singular with respect to some fixed probability measure we supply sufficient conditions for the existence of absolutely continuous conditionally invariant measures. These conditions are satisfied for a wide class of dynamical systems including systems that are Φ-mixing and Gibbs.

Dimensions of random affine code tree fractals

2014

We calculate the almost sure Hausdorff dimension for a general class of random affine planar code tree fractals. The set of probability measures describing the randomness includes natural measures in random $V$-variable and homogeneous Markov constructions.

Finite State Verifiers with Constant Randomness

2012

We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. It turns out that allowing two-way interaction with the prover does not change the class of verifiable languages, and that no polynomially bounded amount of randomness is useful for constant-memory computers when used as language recognizers, or public-coin verifiers.

Branch and bound for the cutwidth minimization problem

2013

The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solu…

Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time

2002

This article presents two algebraic characterizations and two related complete problems for the complexity class DLIN that was introduced in [E. Grandjean, Ann. Math. Artif. Intell., 16 (1996), pp. 183--236]. DLIN is essentially the class of all functions that can be computed in linear time on a Random Access Machine which uses only numbers of linear value during its computations. The algebraic characterizations are in terms of recursion schemes that define unary functions. One of these schemes defines several functions simultaneously, while the other one defines only one function. From the algebraic characterizations, we derive two complete problems for DLIN under new, very strict, and mac…

Generating restricted classes of involutions, Bell and Stirling permutations

2010

AbstractWe present a recursive generating algorithm for unrestricted permutations which is based on both the decomposition of a permutation as a product of transpositions and that as a union of disjoint cycles. It generates permutations at each recursive step and slight modifications of it produce generating algorithms for Bell permutations and involutions. Further refinements yield algorithms for these classes of permutations subject to additional restrictions: a given number of cycles or/and fixed points. We obtain, as particular cases, generating algorithms for permutations counted by the Stirling numbers of the first and second kind, even permutations, fixed-point-free involutions and d…

Random analysis of geometrically non-linear FE modelled structures under seismic actions

1990

Abstract In the framework of the finite element (FE) method, by using the “total Lagrangian approach”, the stochastic analysis of geometrically non-linear structures subjected to seismic inputs is performed. For this purpose the equations of motion are written with the non-linear contribution in an explicit representation, as pseudo-forces, and with the ground motion modelled as a filtered non-stationary white noise Gaussian process, using a Tajimi-Kanai-like filter. Then equations for the moments of the response are obtained by extending the classical Ito's rule to vectors of random processes. The equations of motion, and the equations for moments, obtained here, show a perfect formal simi…