Extension of the ALPHA language to recurrences on sparse periodic domains

ALPHA is a functional language based on systems of affine recurrence equations over polyhedral domains. We present an extension of ALPHA to deal with sparse polyhedral domains. Such domains are modeled by Z-polyhedra, namely the intersection of lattices and polyhedra. We summarize the mathematical closure properties of Z-polyhedra, and we show how the important features of ALPHA, namely normalization, substitution, change of basis, are preserved in the extension