Vol. 16, No. 2, 1966

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 297: 1
Vol. 296: 1  2
Vol. 295: 1  2
Vol. 294: 1  2
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
Other MSP Journals
Semigroups, Presburger formulas, and languages

Seymour Ginsburg and Edwin Spanier

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

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
Milestones
Received: 9 October 1964
Published: 1 February 1966
Authors
Seymour Ginsburg
Edwin Spanier