Reports
Representation Theorem Using DOS Languages ; CU-CS-161-79 Public Deposited
https://scholar.colorado.edu/concern/reports/7w62f9108
- Abstract
- It is demonstrated that every context-free language is a homomorphic image of the intersection of two DOS languages and that every recursively enumerable language is the homomorphic image of the intersection of three DOS languages. It is also proved that by increasing the number of components in the intersections of DOS languages one gets an infinite hierarchy of classes of languages within the class of context-sensitive languages.
- Creator
- Date Issued
- 1979-08-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
representationTheoremUsingDosLanguagesCuCs16179.pdf | 2019-12-21 | Public | Download |