On Termination of Integer Linear Loops

DOI10.1137/1.9781611973730.65zbMath1372.68065arXiv1407.1891OpenAlexW2951018967MaRDI QIDQ5363097

Joao Sousa-Pinto, Joël Ouaknine, James Worrell

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1891

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Loops, quasigroups (20N05) Semialgebraic sets and related spaces (14P10) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Related Items (15)

A Calculus for Modular Loop Acceleration ⋮ Reflections on termination of linear loops ⋮ Reachability Problems for One-Dimensional Piecewise Affine Maps ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ On the Identity Problem for the Special Linear Group and the Heisenberg Group. ⋮ Termination of polynomial loops ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ Unnamed Item ⋮ On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond ⋮ Computing expected runtimes for constant probability programs ⋮ On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond ⋮ Complexity of Restricted Variants of Skolem and Related Problems ⋮ O-Minimal Invariants for Discrete-Time Dynamical Systems ⋮ On eventual non-negativity and positivity for the weighted sum of powers of matrices ⋮ Witness to non-termination of linear programs

This page was built for publication: On Termination of Integer Linear Loops