Hostname: page-component-7b7567c8c-9cwtv Total loading time: 0 Render date: 2026-11-19T19:15:56.671Z Has data issue: false hasContentIssue false

About the decision of reachability for register machines

Published online by Cambridge University Press:  15 February 2003

Véronique Cortier*
Affiliation:
Laboratoire Spécification et Vérification, École Normale Supérieure de Cachan, CNRS, 61 avenue du Président Wilson, 94230 Cachan, France; cortier@lsv.ens-cachan.fr.
Get access

Abstract

We study the decidability of the following problem: given p affine functions ƒ1,...,ƒ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 ƒ1,...,ƒp(in this given order)? We show that this question is decidable for p = 1, 2 and undecidable forsome fixed p.

Information

Type
Research Article
Copyright
© EDP Sciences, 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable