About the decision of reachability 
for register machines

Véronique Cortier

Displaying similar documents to “About the decision of reachability for register machines”

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:

Cycle and Path Embedding on 5-ary N-cubes

Tsong-Jie Lin, Sun-Yuan Hsieh, Hui-Ling Huang (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study two topological properties of the 5-ary -cube $Q_{n}^{5}$ . Given two arbitrary distinct nodes and in $Q_{n}^{5}$ , we prove that there exists an - path of every length ranging from to 5 - 1, where ≥ 2. Based on this result, we prove that $Q_{n}^{5}$ is 5-edge-pancyclic by showing that every edge in $Q_{n}^{5}$ lies on a cycle of every length ranging from to 5.

Minimax nonparametric hypothesis testing for ellipsoids and Besov bodies

Yuri I. Ingster, Irina A. Suslina (2010)

ESAIM: Probability and Statistics

Similarity:

We observe an infinitely dimensional Gaussian random vector where is a sequence of standard Gaussian variables and is an unknown mean. We consider the hypothesis testing problem alternatives $H_{ε, τ} : v \in V_{ε}$ for the sets $V_{ε} = V_{ε} (τ, ρ_{ε}) \subset l_{2}$ . The sets are -ellipsoids of semi-axes with -ellipsoid of semi-axes removed or similar Besov bodies with Besov bodies removed. Here $τ = (κ, R)$ or $τ = (κ, h, t, R); κ = (p, q, r, s)$ are the parameters which define the sets for given radii , 0 < ; is the asymptotical...