Advanced Search

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

We study the decidability of the following problem: given  affine functions ƒ,...,ƒ over ${\mathbb{N}}^k$ and two vectors $v_1,v_2\in {\mathbb{N}}^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 .

In the last decade, formal methods have proved their interest when analyzing security protocols. Security protocols require in particular to reason about the attacker knowledge. Two standard notions are often considered in formal approaches: deducibility and indistinguishability relations. The first notion states whether an attacker can learn the value of a secret, while the latter states whether an attacker can notice some difference between protocol runs with different values of the secret. Several...

In the last decade, formal methods have proved their interest when analyzing security protocols. Security protocols require in particular to reason about the attacker knowledge. Two standard notions are often considered in formal approaches: deducibility and indistinguishability relations. The first notion states whether an attacker can learn the value of a secret, while the latter states whether an attacker can notice some difference between protocol runs with different values of the secret. Several...