Some algorithms to compute the conjugates of episturmian morphisms

Gwenael Richomme

Displaying similar documents to “Some algorithms to compute the conjugates of episturmian morphisms”

About the decision of reachability for register machines

Véronique Cortier (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study the decidability of the following problem: given $p$ affine functions $f_{1}, ..., f_{p}$ over $ℕ^{k}$ and two vectors $v_{1}, v_{2} \in ℕ^{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$ .