THE CLASS OF REGULAR SETS IS PROPERLY CONTAINED IN THE CLASS OF PRIMITIVE RECURSIVE SETS.
Abstract
It was stated in Kleene that every regular set is a primitive recursive set. Since, however, regular sets are certain subsets of a finitely generated free semigroup, while primitive recursive sets are subsets of the natural numbers, the relationship between the two concepts is not obvious. In this paper an appropriate mapping into the natural numbers is introduced, allowing a straightforward proof of titled result. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1969
- Accession Number
- AD0691258
Entities
People
- Gerard P. Weeg
Organizations
- University of Iowa