We investigate the family of semi-linear sets of N-t and Z(t). We study the growth function of semi-linear sets and we prove that such a function is a piecewise quasi-polynomial on a polyhedral partition of N-t. Moreover, we give a new proof of combinatorial character of a famous theorem by Dahmen and Micchelli on the partition function of a system of Diophantine linear equations. (C) 2011 Elsevier B.V. All rights reserved.
Quasi-polynomials, linear Diophantine equations and semi-linear sets / D'Alessandro, Flavio; Benedetto, Intrigila; Stefano, Varricchio. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 416:(2012), pp. 1-16. [10.1016/j.tcs.2011.10.014]
Quasi-polynomials, linear Diophantine equations and semi-linear sets
D'ALESSANDRO, Flavio;
2012
Abstract
We investigate the family of semi-linear sets of N-t and Z(t). We study the growth function of semi-linear sets and we prove that such a function is a piecewise quasi-polynomial on a polyhedral partition of N-t. Moreover, we give a new proof of combinatorial character of a famous theorem by Dahmen and Micchelli on the partition function of a system of Diophantine linear equations. (C) 2011 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
