Affine space

Affine transformation

Algebraic number

Pure mathematics

Discrete mathematics

Dimension (graph theory)

Computer science

Polynomial

Dimension of an algebraic variety

Affine hull

Mathematics

Mathematical analysis

Semigroup

Algebra over a field

We exhibit an algorithm to compute the strongest polynomial (or algebraic) invariants that hold at each location of a given affine program (i.e., a program having only non-deterministic (as opposed to conditional) branching and all of whose assignments are given by affine expressions). Our main tool is an algebraic result of independent interest: given a finite set of rational square matrices of the same dimension, we show how to compute the Zariski closure of the semigroup that they generate.

Polynomial Invariants for Affine Programs