License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.514
URN: urn:nbn:de:0030-drops-39615
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3961/
Go to the corresponding LIPIcs Volume Portal

Ben-Amram, Amir M.

Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)

pdf-format:
49.pdf (0.6 MB)

Abstract

In the theory of discrete-time dynamical systems, one studies the limiting behaviour of processes defined by iterating a fixed function f over a given space. A much-studied 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 integer-valued 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 piecewise-affine ones it is PSPACE-complete. 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. Ben-Amram},
  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 =	{514--525},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3961},
  URN =		{urn:nbn:de:0030-drops-39615},
  doi =		{10.4230/LIPIcs.STACS.2013.514},
  annote =	{Keywords: discrete-time dynamical systems, termination, Collatz problem}
}

Keywords: discrete-time dynamical systems, termination, Collatz problem
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI