Arithmetization of the field of reals  with exponentiation extended abstract

Sedki Boughattas; Jean-Pierre Ressayre

Displaying similar documents to “Arithmetization of the field of reals with exponentiation extended abstract”

An improved derandomized approximation algorithm for the max-controlled set problem

Carlos Martinhon, Fábio Protti (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

A vertex of a graph = () is said to be by $M \subseteq V$ if the majority of the elements of the neighborhood of (including itself) belong to . The set is a in if every vertex $i \in V$ is controlled by . Given a set $M \subseteq V$ and two graphs = ( $V, E_{1}$ ) and = ( $V, E_{2}$ ) where $E_{1} \subseteq E_{2}$ , the consists of deciding whether there exists a sandwich graph = () (, a graph where $E_{1} \subseteq E \subseteq E_{2}$ ) such that is a monopoly in = (). If the answer to the is No, we then consider the , whose objective is to find a sandwich...

An improved derandomized approximation algorithm for the max-controlled set problem

Carlos Martinhon, Fábio Protti (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

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

About the decision of reachability for register machines

Véronique Cortier (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the decidability of the following problem: given affine functions ƒ,...,ƒ over $ℕ^{k}$ and two vectors $v_{1}, v_{2} \in ℕ^{k}$ , is reachable from by successive iterations of ƒ,...,ƒ (in this given order)? We show that this question is decidable for and undecidable for some fixed .