BenAmram, Amir M.
Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
Abstract
In the theory of discretetime dynamical systems, one studies the limiting behaviour of processes defined by iterating a fixed function f over a given space. A muchstudied case involves piecewise affine functions on R^n. Blondel et al. (2001) studied the decidability of questions such as mortality for such functions with rational coefficients. Mortality means that every trajectory includes a 0; if the iteration is seen as a loop while (x \ne 0) x := f(x), mortality means that the loop is guaranteed to terminate.
Blondel et al. proved that the problems are undecidable when the dimension n of the state space is at least two. They assume that the variables range over the rationals; this is an essential assumption. From a program analysis (and discrete Computability) viewpoint, it would be more interesting to consider integervalued variables.
This paper establishes (un)decidability results for the integer setting. We show that also over integers, undecidability (moreover, Pi^0_2 completeness) begins at two dimensions. We further investigate the effect of several restrictions on the iterated functions. Specifically, we consider bounding the size of the partition defining f, and restricting the coefficients of the linear components. In the decidable cases, we give complexity results. The complexity is PTIME for affine functions, but for piecewiseaffine ones it is PSPACEcomplete. The undecidability proofs use some variants of the Collatz problem, which may be of independent interest.
BibTeX  Entry
@InProceedings{benamram:LIPIcs:2013:3961,
author = {Amir M. BenAmram},
title = {{Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {514525},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897507},
ISSN = {18688969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3961},
URN = {urn:nbn:de:0030drops39615},
doi = {10.4230/LIPIcs.STACS.2013.514},
annote = {Keywords: discretetime dynamical systems, termination, Collatz problem}
}
26.02.2013
Keywords: 

discretetime dynamical systems, termination, Collatz problem 
Seminar: 

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Issue date: 

2013 
Date of publication: 

26.02.2013 