A characterization of semilinear sets
Rani Siromoney · Proceedings of the American Mathematical Society · 1969
Introduction. The recent interest in the structure of programming languages has led to the study of their mathematical properties. Characterizations of bounded context-free languages (also called bounded ALGOL-like languages) [1] and bounded regular sets [3] have been given in terms of certain semilinear subsets of Nn. Semilinear sets have been extensively studied as subsets of lattice points in n-space which are finite unions of cosets of finitely generated subsemigroups of the set of all lattice points with nonnegative coordinates and which are also shown to be equivalent to the family of sets defined by modified Presburger formulas [2]. In this note we give a characterization and discuss decision procedures for semilinear sets of words (hereafter called semilinear sets) [4] which include bounded context-free languages and hence bounded regular sets.