All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 20 Next

Displaying 381 – 400 of 532

Showing per page

Signed bits and fast exponentiation

Wieb Bosma (2001)

Journal de théorie des nombres de Bordeaux

An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that...

Similarity relations and cover automata

Jean-Marc Champarnaud, Franck Guingne, Georges Hansel (2005)

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

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate...

Similarity relations and cover automata

Jean-Marc Champarnaud, Franck Guingne, Georges Hansel (2010)

RAIRO - Theoretical Informatics and Applications

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained as immediate...

Smooth and sharp thresholds for random k -XOR-CNF satisfiability

Nadia Creignou, Hervé Daudé (2003)

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

The aim of this paper is to study the threshold behavior for the satisfiability property of a random k -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with k variables per equation. For k ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random k -XOR-CNF formula, whereas there are smooth thresholds for k = 1 and k = 2 .

Some graphic uses of an even number of odd nodes

Kathie Cameron, Jack Edmonds (1999)

Annales de l'institut Fourier

Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.

Space-efficient parallel merging

J. Katajainen, C. Levcopoulos, O. Petersson (1993)

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

Stochastic bottleneck transportation problem with flexible supply and demand quantity

Yue Ge, Hiroaki Ishii (2011)

Kybernetika

We consider the following bottleneck transportation problem with both random and fuzzy factors. There exist m supply points with flexible supply quantity and n demand points with flexible demand quantity. For each supply-demand point pair, the transportation time is an independent positive random variable according to a normal distribution. Satisfaction degrees about the supply and demand quantity are attached to each supply and each demand point, respectively. They are denoted by membership functions...

Currently displaying 381 – 400 of 532