# Polynomial invariants for affine programs

Hrushovski, E
Ouaknine, J
Pouly, A
Worrell, J

9 July 2018

## Journal:

LICS '18 Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

## Last Updated:

2021-06-09T12:02:40.103+01:00

## DOI:

10.1145/3209108.3209142

530-539

## abstract:

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.

842302

Submitted

Conference Paper

9781450355834