Semigroups, Presburger formulas, and languages
Seymour Ginsburg, Edwin H. Spanier · Pacific Journal of Mathematics · 1966
An interesting class of subsets of lattice points in %-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.The class of semilinear sets, first considered in [3] was extensively