Title: Complexity Measures for Affine Counter Systems Context

Affine counter systems manipulate non-negative integer variables through linear updates. They are used to model various classes of systems [1], and enjoy a few decidable properties thanks to a well quasi ordering (wqo) over their state space: termination (can the system run indefinitely?) and safety (can the system enter an unsafe state?) are decidable. Recent work on the complexity of algorithms that rely on wqos for their ter-mination shows that these problems are complete for Ackermannian time/space resources [5]. Objectives The purpose of this internship is to initiate a study of 1. how measures developed in the implicit complexity community for primitive-recursive functions [2, 4] could be adapted in the context of affine counter systems, 2. whether the systems found in benchmarks [1] enjoy small measures, and 3. decision procedures for polynomial termination [3] if time allows. Prerequisites Basics in complexity, recursion, and logic. Contac