Computing the jth solution  of a first-order query

Guillaume Bagan; Arnaud Durand; Etienne Grandjean; Frédéric Olive

Displaying similar documents to “Computing the jth solution of a first-order query ”

An Upper Bound on the Space Complexity of Random Formulae in Resolution

Michele Zito (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in -CNF on variables and clauses is $O (n \cdot Δ^{- \frac{1}{k - 2}})$ .

Finding the principal points of a random variable

Emilio Carrizosa, E. Conde, A. Castaño, D. Romero–Morales (2010)

RAIRO - Operations Research

Similarity:

The -principal points of a random variable with finite second moment are those points in $ℝ$ minimizing the expected squared distance from to the closest point. Although the determination of principal points involves in general the resolution of a multiextremal optimization problem, existing procedures in the literature provide just a local optimum. In this paper we show that standard Global Optimization techniques can be applied.

A Compositional Approach to Synchronize Two Dimensional Networks of Processors

Salvatore La Torre, Margherita Napoli, Mimmo Parente (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The problem of synchronizing a network of identical processors that work synchronously at discrete steps is studied. Processors are arranged as an array of rows and columns and can exchange each other only one bit of information. We give algorithms which synchronize square arrays of ( × ) processors and give some general constructions to synchronize arrays of ( × ) processors. Algorithms are given to synchronize in time , $n ⌈ log n ⌉$ , $n ⌈ \sqrt{n} ⌉$ and 2 a square array of ( × ) processors. Our...