On-line finite automata for addition 
in some numeration systems

Christiane Frougny

Displaying similar documents to “On-line finite automata for addition in some numeration systems”

Computing the prefix of an automaton

Marie-Pierre Béal, Olivier Carton (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We present an algorithm for computing the prefix of an automaton. Automata considered are non-deterministic, labelled on words, and can have -transitions. The prefix automaton of an automaton $𝒜$ has the following characteristic properties. It has the same graph as $𝒜$ . Each accepting path has the same label as in $𝒜$ . For each state , the longest common prefix of the labels of all paths going from to an initial or final state is empty. The interest of the computation of the prefix...

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 .

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:

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...