An interesting class of subsets
of lattice points in n-space arises naturally in the mathematical theory of
(context free) languages. This is the class of semilinear subsets, a subset of
lattice points being semilinear if it is the finite union of cosets of finitely
generated sub-semigroups of the set of all lattice points with nonnegative
coordinates.
The family of semilinear sets is here shown to be equivalent to the family of sets
defined by modified Presburger formulas. A characterization of those semilinear sets
which correspond to languages is then given. Finally, using the two preceding results
and the known decidability of the truth of a modified Presburger sentence, a decision
procedure is given for determining whether an arbitrary linear set corresponds to a
language.
