Vol. 16, No. 2, 1966

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 294: 1
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
Author Index
To Appear
ISSN: 0030-8730
Semigroups, Presburger formulas, and languages

Seymour Ginsburg and Edwin Spanier

Vol. 16 (1966), No. 2, 285–296

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.

Mathematical Subject Classification
Primary: 94.50
Received: 9 October 1964
Published: 1 February 1966
Seymour Ginsburg
Edwin Spanier